#include <bits/stdc++.h>
using namespace std;
using VI = vector<int>;
using ll = long long;
using PII = pair<int,int>;
const int mod = 19650827;
int n,k;
ll m;
int a[50010];
int b[50010];
int del[50010];
int main(){
cin>>n>>k>>m;
priority_queue<PII,vector<PII>,greater<PII>>p1,p2;
priority_queue<int,vector<int>,greater<int>>p3;
for(int i=1;i<=n;i++) {
cin>>a[i]>>b[i];
p1.push({a[i],i});
p2.push({b[i],i});
}
for(int i=1;i<=k;i++) p3.push(0);
ll res = 0;
int ct = 0;
while (ct < n){
while(del[p1.top().second] == 1) p1.pop();
while(del[p2.top().second] == 1) p2.pop();
auto x = p1.top();
auto y = p2.top();
auto z = p3.top();
if(x.first > y.first + z){
del[y.second] = 1;
p2.pop();
int d = a[y.second] - b[y.second];
p3.pop();
p3.push(d);
res += y.first + z;
}else{
del[x.second] = 1;
p1.pop();
res += x.first;
}
if(res > m){
break;
}else{
ct++;
}
}
cout<<ct;
}
利用差值来表示更换优惠卷的操作
比如你现在已经用了k张优惠卷，如果你想要用更换优惠卷，就用补差价，文章来源：https://www.toymoban.com/news/detail-651132.html
如果补的差价＋物品的优惠值 <= 直接再买一个（和前面的物品并不是同一个） 那就直接不用优惠卷买文章来源地址https://www.toymoban.com/news/detail-651132.html
到了这里，关于P3045 [USACO12FEB] Cow Coupons G ( 反悔堆的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
![【LeetCode】数据结构题解（12）[用栈实现队列]](https://imgs.yssmx.com/Uploads/2024/02/635811-1.png)
