codeforces div2 PriceFixed 补题

思路：
贪心 + 排序 + 双指针算法
先按bi的数量从大到小排序，然后排序ai，然后运用双指针，如果购买的商品数可以买最低需要的商品数打折就一直买，否则的话从最后面购买商品使得前面的商品可以构成打折，然后把后面的买完的数量就清除掉。
代码：

```cpp
#include <bits/stdc++.h>

using namespace std;
typedef unsigned long long LL;
const int N = 2e5+10;
int t;
typedef pair<LL,LL> PII;


int main()
{
    ios::sync_with_stdio(false); cin.tie(0);
    int n; cin>>n;
    vector <PII> q(n);
    for(int i=0;i<n;i++) cin>>q[i].second>>q[i].first;
        
    sort(q.begin(),q.end());
    int l = 0,r = n-1;
    LL ans = 0,sum = 0;
    while(l<=r)
    {
        while(l<=r&&q[l].first<=ans)  //如果符合打折情况就进行打折
        {
            ans+=q[l].second;
            sum+=q[l].second;
            q[l].second = 0;
            l++;
        }
        while(r>=l&&q[r].second==0) r--;  //除去后面已经买完的点
        if(l>r) break;
        LL cnt = min(q[l].first-ans,q[r].second); //取后面最后成立的几个商品来凑成当前的商品可以打折
        q[r].second-=cnt;
        sum+=(cnt*2);
        ans+=cnt;
    }
    cout<<sum<<endl;
    return 0;
}

最后

以上就是长情歌曲为你收集整理的codeforces div2 PriceFixed 补题的全部内容，希望文章能够帮你解决codeforces div2 PriceFixed 补题所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。