【贪心】购买书籍

题面

L的书籍被M偷了以后伤心欲绝,决定再购买一些回来,现在有 N 本书可以买,每本书的价格是 a[i]元。 现在L总共有 M 元,以及 K 张优惠券。 对于每本书,如果使用一张优惠券,则可以用b[i]的优惠价格购买。 注意每本书只能使用一张优惠券,只能购买一次。 L想知道自己最多可以购买几本书?

输入

第一行三个整数 N, K, M 接下来 N 行,每行两个整数,表示 a[i]和 b [i]。

输出

一个整数表示答案。

样例输入

4 1 7
3 2
2 2
8 1
4 3

样例输出

3

提示 【解释】 选择第 1、 2、 3 本书,其中第3本使用优惠券。总共 5 元。 【数据规模】 对于 20%:N<=10 对于 50%:N<=100 对于另外 20%:K = 0 对于 100%:1<=N<=100000,0<=K<=N,M<=1014,1<=b[i]<=a[i]<=109 标签

解答

感谢熊姐姐的题解Orz,太聚了。贪心题,不算特别难想,但是我也想不到。。。。于是随机化贪心过了。。。。。。。。。zxy的hack数据也没hack掉(蒟蒻光环) 先说随机化贪心的方法,先按照优惠价排序,按照优惠价购买,买完以后如果有剩余的钱就按照原价最小买Orz。然后由于我感觉不太稳,把原序列random_shuffle一下,再多跑几遍,跑的时候2种策略计算答案,就A了。你来卡我啊 贴随机化贪心代码:前面还有一通乱搞乱排序

# include <algorithm>
# include <iostream>
# include <cstring>
# include <cstdio>
# include <ctime>
using namespace std;
const int MAXN = 100010;
long long n,m,k;
struct book{
	long long a,b;
}bs[MAXN];
bool cmp1(book &b1,book &b2){
	return b1.a<b2.a;
}
bool cmp2(book &b1,book &b2){
	return b1.b<b2.b;
}
bool cmp3(book &b1,book &b2){
	return b1.a-b1.b<b2.a-b2.b;
}
bool cmp4(book &b1,book &b2){
	return b1.a*b1.b<b2.a*b2.b;
}
bool cmp5(book &b1,book &b2){
	return b1.a/b1.b<b2.a/b2.b;
}
long long work(){
	long long sum = m,tot = 0,used = 0;
	for(int i = 1;i<=n;i++){
		if(sum>=bs[i].a)tot++,sum-=bs[i].a;
		else if(used<k&&sum>=bs[i].b)used++,sum-=bs[i].b,tot++;
	}
	long long ret = tot;
	sum = m,tot = 0,used = 0;
	for(int i = 1;i<=n;i++){
		if(sum>=bs[i].b&&used<k)tot++,sum-=bs[i].b,used++;
		else if(sum>=bs[i].a)used++,sum-=bs[i].a,tot++;
	}
	return max(tot,ret);
}
int main(){
	# ifdef BEYONDSTARS
		freopen("testdata.in","r",stdin);
	# endif
	srand(time(0));
	scanf("%lld %lld %lld",&n,&k,&m);
	for(int i = 1;i<=n;i++){
		scanf("%lld %lld",&bs[i].a,&bs[i].b);
	}
	long long ans = work();
	sort(bs+1,bs+1+n,cmp1);ans = max(ans,work());
	sort(bs+1,bs+1+n,cmp2);ans = max(ans,work());
	sort(bs+1,bs+1+n,cmp3);ans = max(ans,work());
	sort(bs+1,bs+1+n,cmp4);ans = max(ans,work());
	sort(bs+1,bs+1+n,cmp5);ans = max(ans,work());

	if(n>5000){
		for(int i = 1;i<=200;i++){
			random_shuffle(bs+1,bs+1+n);ans = max(ans,work());
		}
	}else{
		for(int i = 1;i<=5000;i++){
			random_shuffle(bs+1,bs+1+n);ans = max(ans,work());
		}
	}
	printf("%lld",ans);
	return 0;
}

正解:还是贪心,就是优先购买优惠价低的,然后对于剩下的东西,从原价最小开始枚举,看看是把之前用了券的退掉,这个东西用优惠价便宜还是直接买便宜。于是3个set维护差值,优惠价,原价就好了。Orz wtcl

# include <algorithm>
# include <iostream>
# include <cstring>
# include <cstdio>
# include <queue>
# include <set>
using namespace std;
typedef pair<int,int> pii;
const int MAXN = 100010;
long long a[MAXN],b[MAXN],id[MAXN];
set<pii> s1,s2,s3;
bool cmp(int x,int y){return b[x]<b[y];}
int main(){
	int n,k;long long m;scanf("%d %d %lld",&n,&k,&m);
	for(int i = 1;i<=n;i++)scanf("%lld %lld",&a[i],&b[i]),id[i] = i;
	sort(id+1,id+1+n,cmp);
	int ans = 0;
	if(k==0){
		sort(a+1,a+1+n);
		for(int i = 1;i<=n;i++){
			if(m>a[i])ans++,m-=a[i];
			else break;
		}
		printf("%d",ans);return 0;
	}
	long long now = 0;
	for(int i = 1;i<=k;i++){
		now+=b[id[i]];if(now>m){printf("%d",ans);return 0;}
		ans++;
		s1.insert(make_pair(a[id[i]]-b[id[i]],id[i]));
	}
	for(int i = k+1;i<=n;i++){
		s2.insert(make_pair(b[id[i]],id[i]));
		s3.insert(make_pair(a[id[i]],id[i]));
	}
	while(s2.size()){
		long long f1 = s1.begin()->first+s2.begin()->first,f2 = s3.begin()->first;
		if(f1<f2){
			now+=f1;
			if(now>m)return 0*printf("%d",ans);
			ans++;
			int id_ = s2.begin()->second;
			s1.erase(s1.begin());s2.erase(s2.begin());
			s3.erase(s3.find(make_pair(a[id_],id_)));
			s1.insert(make_pair(a[id_]-b[id_],id_));
		}else{
			now+=f2;if(now>m)return 0*printf("%d",ans);
			ans++;
			int id_ = s3.begin()->second;
			s2.erase(s2.find(make_pair(b[id_],id_)));s3.erase(s3.begin());
		}
	}
	printf("%d",ans);
	return 0;
}