FJ看中了N(1 <= N <= 50,000)头牛，他有m (1 <= M <= 10^14)元，还有k(1 <= K <= N)张优惠券。
第i头牛的价格为P_i (1 <= P_i <= 10^9)，如果使用优惠券则为C_i (1 <= C_i <= P_i)。问农夫最多能买到多少头牛。
Input
* 行1: 三个整数: N, K, and M.
* 行2..N+1: 每行两个整数 P_i 和 C_i.
Output
一个整数为买到牛数量
Sample Input
4 1 7
3 2
2 2
8 1
4 3
Sample Output
3
样例说明:
将优惠卷用在第三头牛身上，付出1元，再买前两头牛付出3+2=6元，共支出7元，买到3头牛
Sol:
可以认为买每头牛都用到了优惠卷，只是最开始的优惠卷支出是0元，后面的就要付出代价了。所以我们在买牛时，如果是原价买自然要买最便宜的，如果是用优惠价来买，也是买最便宜的，当然此时要用到优惠券，优惠券自然也要用最便宜的了.所以对于每次购买讨论下看是直接买，还是优惠价+优惠券哪种更便宜，当然这两种方式可能买得并不是同一种物品哟。
#include<queue>
#include<cstdio>
#include<algorithm>
using namespace std;
struct node
{
int num, id;
};
bool operator < (node x, node y)
{
return x.num > y.num;
}
priority_queue<node> q1, q2; //重载运算符后成为小根堆
priority_queue<int, vector<int>, greater<int> > q3;
//定义一个小根堆
int N, K, ans;
long long M;
int use[150001], p[150001], q[150001];
int main()
{
scanf("%d %d %lld", &N, &K, &M);
//N个物品，k张优惠卷,M元钱
for (int i = 1; i <= N; i++)
{
scanf("%d %d", &p[i], &q[i]);
q1.push((node){p[i], i});//放原价
q2.push((node){q[i], i});//放优惠价
}
for (int i = 1; i <= K; i++)
q3.push(0);//一开始有k张优惠券,价格为0
for (; M > 0 && ans < N; )
{
while (use[q1.top().id])
q1.pop();
while (use[q2.top().id])
q2.pop();
if (q1.top().num <= q2.top().num + q3.top())
{//q1这个堆中放的是如果直接买的话，最便宜的
//q2放的是如果使用优惠券的话，最便宜的
//对于优惠券我们可以认为开始价格为0，如果如果要赎回的话，自然也是赎回代价最小的
node x = q1.top();
M -= x.num;
if (M < 0) break;
use[x.id] = 1;
q1.pop();
ans++;
}
else {//花券买
node x = q2.top();
M -= x.num + q3.top();
if (M < 0) break;
use[x.id] = 1;
q3.pop();
q3.push(p[x.id] - q[x.id]);
//新放入这个物品可撤回的优惠券
q2.pop();
ans++;
}
}
printf("%d", ans);
} Sol2:
4 1 15//4头牛，1个优惠券，15元钱
10 2
你会发现，我们会尽量用优惠券去买东西。买什么样的东西呢，当然是便宜的。
于是我们可以按优惠价从小到大排序，再来买。
但先用优惠券买第三头，再接下来只能买第一头和第二头了。
但事实上，是可以四头牛都可以买的。
所以这需要一个后悔操作。
如何后悔呢？
我们可以用优惠价买第三头牛，将差价8-1=7丢一个小根堆中。
然后对于剩下的三头牛按原价进行排序得到
对于
2 2这头牛，发现要么原价买，要么赎回优惠券（代价为7),然后再用优惠价来买
但明显2<2+7,所以干脆原价买
这头牛，也是同理
但对于
10 2这头牛
10<2+7的，于是
//针对前K个物品全用上优惠券，但将原价-优惠价丢到堆中。再针对第k+1到N的物品，看是原价买合适还是赎回券，这样就可以用优惠价买了。还是用原价来买。
#include<cmath>
#include<queue>
#include<vector>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define pa pair<int,int>
#define inf 1000000000
#define eps 1e-8
#define ll long long
using namespace std;
ll read()
{
ll x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
priority_queue<int,vector<int>,greater<int> >q;
int n,K,ans;
ll m,sum;
struct data{
int p,c;
}a[50005];
bool cmpc(data a,data b)
{
return a.c<b.c;
}
bool cmpp(data a,data b)
{
return a.p<b.p;
}
int main()
{
n=read();K=read();m=read();
for(int i=1;i<=n;i++)
a[i].p=read(),a[i].c=read();
sort(a+1,a+n+1,cmpc);//按优惠价进行升序排列
for(int i=1;i<=K;i++) //尽量使用优惠券买
{
sum+=a[i].c;
q.push(a[i].p-a[i].c);
if(sum>m) //如果花的钱已超过m，但券还没有花完，则输出i-1
{
printf("%d\n",i-1);
return 0;
}
if(i==n) //如果全部买下来了
{
printf("%d\n",n);
return 0;
}
}
sort(a+K+1,a+n+1,cmpp);//按原价进行升序排列
ans=K;
for(int i=K+1;i<=n;i++)
{
int t=inf;
if(!q.empty())t=q.top();
if(a[i].c+t<a[i].p) //如果原价更高的话
{
sum+=t;//赎回一张优惠券
q.pop();
q.push(a[i].p-a[i].c);
sum+=a[i].c;//支出优惠价
}
else //按原价进行购买
sum+=a[i].p;
if(sum>m)
break;
else
ans++;
}
printf("%d\n",ans);
return 0;
}