Cow Coupons G

link

一道贪心题。

首先作为一个正常人，有优惠券肯定会尽量用（题目中保证了优惠价格不会比原价高），于是考虑先把所有优惠券都全部用完。在用完所有优惠券之后如果还有闲钱，那么就会考虑入手新牛。发现有两种决策，一种是用原价买已经买过的特价牛，空出来的优惠券去买另一头牛，代价是 \(a_i-b_i+b_j\) ；另一种决策是用原价再买一头牛，代价是 \(a_i\) 。发现两个都是可以贪心取最小值的，于是就一直累加最小代价，不断更新答案一直到牛被买完或者没钱了结束。

#include
//#define zczc
#define int long long
const int N=50010;
using namespace std;
inline void read(int &wh){
    wh=0;int f=1;char w=getchar();
    while(w<'0'||w>'9'){if(w=='-')f=-1;w=getchar();}
    while(w<='9'&&w>='0'){wh=wh*10+w-'0';w=getchar();}
    wh*=f;return;
}

int m,n,my;
struct node{
	int a,b;
}a[N];
inline bool cmp1(node s1,node s2){
	return s1.bq1,q2,q3;

bool ch[N];

signed main(){
	
	#ifdef zczc
	freopen("in.txt","r",stdin);
	#endif
	
	read(m);read(n);read(my);
	for(int i=1;i<=m;i++){
		read(a[i].a);read(a[i].b);
	}
	sort(a+1,a+m+1,cmp1);
	int use=0,pl,ans;
	for(pl=1;pl<=n;pl++){
		use+=a[pl].b;
		if(use>my){printf("%lld",pl-1);return 0;}
		q1.push((node){pl,a[pl].a-a[pl].b});
	}
	ans=pl-1;
	//printf("now use %lld\n",use);
	for(int i=pl;i<=m;i++){
		q2.push((node){i,a[i].a});
		q3.push((node){i,a[i].b});
	}
	while(use=my){
			printf("%lld",ans-(use>my));
			return 0;
		}
	}
	
	return 0;
}