牛券

题目描述

Farmer John needs new cows! There are $N$ cows for sale $(1 \le N \le 50,000)$, and FJ has to spend no more than his budget of $M$ units of money $(1 \le M \le 10^{14})$. Cow $i$ costs $P_i$ money $(1 \le P_i \le 10^9)$, but FJ has $K$ coupons $(1 \le K \le N)$, and when he uses a coupon on cow $i$, the cow costs $C_i$ instead $(1 \le C_i \le P_i)$. FJ can only use one coupon per cow, of course.
What is the maximum number of cows FJ can afford?
FJ准备买一些新奶牛，市场上有$N$头奶牛$(1 \le N \le 50000)$，第i头奶牛价格为$Pi(1 \le Pi \le 10^9)$。FJ有$K$张优惠券，使用优惠券购买第$i$头奶牛时价格会降为$Ci(1 \le Ci \le Pi)$，每头奶牛只能使用一次优惠券。FJ想知道花不超过$M(1 \le M \le 10^{14})$的钱最多可以买多少奶牛？

输入格式

• Line $1$: Three space-separated integers: $N$, $K$, and $M$.
• Lines $2~N+1$: Line $i+1$ contains two integers: $P_i$ and $C_i$.

输出格式

• Line $1$: A single integer, the maximum number of cows FJ can afford.

样例输入

4 1 7
3 2
2 2
8 1
4 3


样例输出

3


说明/提示

FJ has $4$ cows, $1$ coupon, and a budget of $7$.
FJ uses the coupon on cow $3$ and buys cows $1$,$2$ and $3$, for a total cost of $3+2+1=6$.

题解

1. 用原价购买这个牛
2. 在已使用优惠券的牛中选择一个牛，使得这个牛不适用优惠券后增加的价格最小，把这个牛的优惠券给当前牛用。
注：以上两种情况都要在钱够用的情况下

#include<bits/stdc++.h>
#include<queue>
using namespace std;
int n,k;
long long m;
struct aa{
int p,c;
}a[50009];
int ans;
priority_queue<int,vector<int>,greater<int> >q;
bool cmp(aa x,aa y){return x.c<y.c;}
int main(){
scanf("%d%d%lld",&n,&k,&m);
for(int j=1;j<=n;j++)
scanf("%d%d",&a[j].p,&a[j].c);
sort(a+1,a+n+1,cmp);
for(int j=1;j<=n;j++){
if(k){
if(m-a[j].c<0) continue;
k--;
m-=a[j].c;
q.push(a[j].p-a[j].c);
ans++;
}else{
if(m-min(a[j].p,a[j].c+q.top())<0) continue;
m-=min(a[j].p,a[j].c+q.top());
ans++;
if(a[j].p-a[j].c>q.top()){
q.pop();
q.push(a[j].p-a[j].c);
}
}
}
printf("%d",ans);
return 0;
}