codeforces div2 PriceFixed 补题

104 阅读 0 评论 69 点赞

我是靠谱客的博主长情歌曲，这篇文章主要介绍codeforces div2 PriceFixed 补题，现在分享给大家，希望可以做个参考。

在这里插入图片描述

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

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

```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;
}