购买巧克力
时间限制: 1 Sec 内存限制: 128 MB
[提交] [状态]
题目描述
SHOI这次科技竞赛取得了好成绩，想庆祝一番，他手头总共有M元，购买巧克力来让同学分享快乐。他在SH商店逸择购买，在巧克力商品柜中共有N块巧克力，每块巧克力的价格是a[i］元．商家为了促销，提供给他K张优惠券，使用方法是：对于每块巧克力，如果使用一张优惠券，则可以以b[i］的优惠价格购买．注意每块巧克力只能使用一张优惠券，只能购买一次。
SHOI想知道自己最多可以购买多少块巧克力？
输入
第一行三个整数N,K,M(0≤K≤N≤100000,M≤1014）。接下来N行，每行两个整数，表示a[i]和bi。
输出
一个整数表示最多购买巧克力数。
样例输入 Copy
4 1 7
3 2
2 2
8 1
4 3
样例输出 Copy
3
提示
样例解释：选择第1、2、3块巧克力，其中第三块使用优惠券，总共5元。
对于20%的数据N≤10。
对于50%的数据:N≤100
对于100%的数据:N≤100000
又被贪心搞了，wa7次
思路：
很简单的思路，先把所有的优惠券都用完，要想要花钱最少并且数量最多的话，就按照b排序。
然后再从剩下的商品里看最多能买多少，这时候就需要按照a排序了。
要注意一个商品只能用一次，所以要再加个标记。
菜的真实
#include<bits/stdc++.h> using namespace std; typedef long long ll; inline 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; } const int maxn=1e6+7; ll n,k,m; struct node{ ll a,b; ll flag;///记录是否被用过 }; node a[maxn]; bool cmp1(node a,node b){ return a.b<b.b; } bool cmp2(node a,node b){ if(a.flag==b.flag) return a.a<b.a; return a.flag<b.flag; } int main(){ n=read();k=read();m=read(); for(int i=1;i<=n;i++){ a[i].a=read();a[i].b=read(); } sort(a+1,a+1+n,cmp1); int res=0; for(int i=1;i<=k;i++){ if(a[i].b<=m){ m-=a[i].b; a[i].flag=1; res++; } } if(m<=0){ cout<<res<<endl; return 0; } sort(a+1,a+1+n,cmp2); for(int i=1;i<=n;i++) if(!a[i].flag){ if(a[i].a<=m){ m-=a[i].a; res++; } if(m<=0){ cout<<res<<endl; return 0; } } cout<<res<<endl; return 0; }
