小X 希望尽可能多地满足小Y 的愿望，所以小X 想要知道他至多能购买多少件商品。
今天第一题题答题，第二题傻逼题，第三题卡常题
让后
第一题推了个错误的贪心，60pts
第二题出题人出了三个很强的数据卡哈希（好险我写了也交了sam，拿哈希对拍）
第三题，map启发式合并，各种sb错误
结果160pts滚粗
先说说这题的正解（好傻啊为什么想不到可撤回贪心）
我们开三个堆q1,q2,q，分别存p[i],q[i]，第三个堆一开始有k个零（相当于k张优惠券）
每次拿出q2+q和q1中的较小值，让后如果拿出的是q2+q，那就向q中丢一个p[i]-q[i]（相当于可以撤回）
直到拿出来，钱还不够就退出
哇现在才发现好好写啊！
#include<queue>
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
struct pr{ int x,y; } x;
inline bool operator< (pr a,pr b){ return a.x>b.x; }
priority_queue<pr> q1,q2;
priority_queue<int,vector<int>,greater<int> > q;
int n,k,p[50010],c[50010],v[50010]; long long m;
int main(){
freopen("shopping.in","r",stdin);
freopen("shopping.out","w",stdout);
scanf("%d%d%lld",&n,&k,&m);
for(int i=n;i;--i) scanf("%d%d",p+i,c+i);
for(int i=k;i;--i) q.push(0);
for(int i=n;i;--i){
q1.push((pr){p[i],i});
q2.push((pr){c[i],i});
}
int ans=0;
for(;m>0 && ans<n;++ans){
for(;v[q1.top().y];q1.pop());
for(;v[q2.top().y];q2.pop());
if(q.top()+q2.top().x<q1.top().x){
x=q2.top();
m-=x.x+q.top();
if(m<0) break;
q.pop(); q.push(p[x.y]-c[x.y]);
v[x.y]=1; q2.pop();
} else {
x=q1.top();
m-=x.x;
if(m<0) break;
v[x.y]=1; q1.pop();
}
}
printf("%d
",ans);
}