【经典】有K张折扣券和m元最多能买多少物品（折前价ai，折后价bi

这真是很玄学的一道题，贪心也要贪好几次。。。

题解：http://www.voidcn.com/article/p-eincjhrs-rv.html

题解：http://www.voidcn.com/article/p-yrbutkck-up.html

#include<bits/stdc++.h>
#define ll long long
using namespace std;
struct node{
	int a,b;
}x[100005];
struct node2{
	int a,b,c;
}y[100005],z[100005];
int vis[100005];
int cmp1(node a,node b){
	if(a.b!=b.b)
		return a.b<b.b;
	return a.a<b.a;
}
int cmp2(node2 a,node2 b){
	if(a.b!=b.b)
		return a.b<b.b;
	if(a.a!=b.a)
		return a.a<b.a;
	return a.c<b.c;
}
int cmp3(node2 a,node2 b){
	if(a.a!=b.a)
		return a.a<b.a;
	if(a.b!=b.b)
		return a.b<b.b;
	return a.c<b.c;
}
struct cmp{  
   bool operator()(const int &t1,const int &t2){  
        return t1>t2;  //从小到大，与数组规则相反   
   }
};  
int main(){
	int t;
	cin>>t;
	while(t--){
		priority_queue<node,vector<int>,cmp> q; 
		int n,k;
		ll m;
		cin>>n>>k>>m;
		for(int i=0;i<n;++i){
			cin>>x[i].a>>x[i].b;
		}
		sort(x,x+n,cmp1); //按b排序 
		ll s=0;
		int p=0;
		for(int i=0;i<k;++i){
			s+=x[i].b;
			if(s>m)
				break;
			p++;
		}
		if(s>m){
			cout<<p<<endl;
			continue;
		}
		for(int i=0;i<k;++i){
			q.push(x[i].a-x[i].b);
		}
		for(int i=k;i<n;++i){
			y[i-k]={x[i].a,x[i].b,i-k};
			z[i-k]={x[i].a,i-k};
		}
		sort(y,y+(n-k),cmp3); //按a排序 
		sort(z,z+(n-k),cmp2); //按b排序 
		memset(vis,sizeof(vis));
		int a=0,b=0; 
		for(int i=0;i<n-k;++i){
			while(vis[y[a].c]) a++;
			while(vis[z[b].c]) b++;
			if(!q.empty()){
				int fr=q.top();
				if(z[b].b+fr<=y[a].a){ //比较【折前价最低】和【转移折扣券补差价】哪个低
					s+=z[b].b+fr;
					if(s>m) break;
					p++;
					q.pop();
					q.push(z[b].a-z[b].b);
					vis[z[b].c]=1;
				}
				else{
					s+=y[a].a;
					if(s>m) break;
					p++;
					vis[y[a].c]=1;
				}
			}
			else{ //这个情况不要忽略（k=0时队列为空） 
				s+=y[a].a;
				if(s>m) break;
				p++;
				vis[y[a].c]=1;
			}
		}
		cout<<p<<endl;
	}
	return 0;
}

（编辑：娄底站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!