Description
X 城的商场中，有着琳琅满目的各种商品。一日，小X 带着小Y 前来购物，小Y 一共看中了n件商品，每一件商品价格为Pi。小X 现在手中共有m个单位的现金，以及k 张优惠券。小X 可以在购买某件商品时，使用至多一张优惠券，若如此做，该商品的价格会下降至Qi。
小X 希望尽可能多地满足小Y 的愿望，所以小X 想要知道他至多能购买多少件商品。
Input
第一行包含三个整数n,k,m，表示商品总数，小X 拥有的优惠券与现金总数。
接下来n行每行包含两个整数Pi,Qi。
Output
共一行包含一个整数，表示小X 至多能购买的物品数。
Sample Input
4 1 7
3 2
2 2
8 1
4 3
Sample Output
3
样例解释：一种最优的购买方式是购买1,2,3号物品，并用优惠券购买物品3，总共花费为3+2+1=6。
解题思路
贪心，首先按照优惠价排序，之后用一个优先队列去维护一个size为k的差价，表示这k个买优惠价，每次看新加入的是否更优。之后再用一个优先队列存用原价买的，时间复杂度O(nlogn)
代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<cstdlib>
#include<queue>
using namespace std;
const int MAXN = 50005;
typedef long long LL;
inline LL rd(){
LL x=0,f=1;char ch=getchar();
while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
while(isdigit(ch)) {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
return x*f;
}
struct Data{
int diff;
LL a,q;
bool operator < (const Data A)const{
return A.diff<=diff;
}
}data[MAXN];
int n,k;
LL m,ans,sum;
priority_queue<Data> Q;
priority_queue<LL> q;
inline bool cmp(Data A,Data B){
return A.q<B.q;
}
int main(){
freopen("shopping.in","r",stdin);
freopen("shopping.out","w",stdout);
n=rd();k=rd();m=rd();
for(register int i=1;i<=n;i++) {
data[i].a=rd();
data[i].q=rd();
data[i].diff=data[i].a-data[i].q;
}
sort(data+1,data+1+n,cmp);
for(register int i=1;i<=n;i++){
if(Q.size()<k && data[i].q+sum<=m) {
Q.push(data[i]);
sum+=data[i].q;
ans++;
}
else if(Q.size()==k){
Data x=Q.top();
if(x.diff+data[i].q<data[i].a){
Q.pop();Q.push(data[i]);
sum=sum-x.q+data[i].q;
if(sum+x.a<=m) {
sum+=x.a;
ans++;
q.push(x.a);
}
else if(!q.empty() && q.top()>x.a){
int y=q.top();q.pop();q.push(x.a);
sum=sum-y+x.a;
}
}
else if(sum+data[i].a<=m) {
sum+=data[i].a;
q.push(data[i].a);
ans++;
}
else if(!q.empty() && q.top()>data[i].a){
int y=q.top();q.pop();q.push(data[i].a);
sum=sum-y+data[i].a;
}
}
}
cout<<ans<<endl;
return 0;
}