nkrq-4315 购买糖果

问题描述

        有N 块糖果，每块糖果的价格是a[i]元。
        总共M 元，以及K 张优惠券。
        对于每块糖果，如果使用一张优惠券，则可以以b[i]的优惠价格购买。
        注意每块糖果只能使用一张优惠券，只能购买一次。
        最多可以购买几块糖果？

输入格式

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

输出格式

        一个整数表示答案。

样例输入

4 1 7
3 2
2 2
8 1
4 3

样例输出

3

目录

                                                     基本思路

                                                        代码

                                                     代码注解

基本思路

这一道题一看就是一道贪心的题目；（最开始我只写了一次贪心->80分）

因为这道题有优惠卷这一形式的存在，所以并不能用一次贪心解决问题（不然很难判断这个糖果买不买，用不用优惠卷）所以这里面要思考一下可不可以分成两部分来分别去贪心；

1. 按优惠价排序并尽量用完优惠卷；
2. 用结构体优先队列q存储剩下东西的优惠差价，并分别用优惠价排序（Z）原价排序（Y）；
3. 循环比较剩下的该用优惠价还是原价（注意：当差值队列变空仍然要考虑，不能省略）；

 所以得到贪心策略：对于以优惠价排序的前n个糖果，能拿多少拿多少，对于剩下的糖果，比较其性价比和原价，选择最后能达到最少价格的一个糖果，并将其标记；

代码

#include<bits/stdc++.h>
using namespace std;
int n,k,ans=0,vis[100005];
long long my=0,m;
struct lyt{
	int a,b;
}x[100005];
struct lyt2{
	int a,b,c;
}y[100005],z[100005];
struct cmp{  
   bool operator()(const int &t1,const int &t2){  
        return t1>t2; 
   }
};
priority_queue<lyt,vector<int>,cmp> q;  
bool cmp1(lyt a,lyt b){
	if(a.b!=b.b)
		return a.b<b.b;
	return a.a<b.a;
}
bool cmp2(lyt2 a,lyt2 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;
}
bool cmp3(lyt2 a,lyt2 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;
} 
int main(){
	cin>>n>>k>>m;
	for(int i=0;i<n;++i){
		cin>>x[i].a>>x[i].b;
	}
	sort(x,x+n,cmp1);
	for(int i=0;i<k;++i){
		my+=x[i].b;
		if(my>m)
			break;
		ans++;
	}
	if(my>m){
		cout<<ans<<endl;
		return 0;
	}
	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].a=x[i].a;
		y[i-k].b=x[i].b;
		y[i-k].c=i-k;
		z[i-k].a=x[i].a;
		z[i-k].b=x[i].b;
		z[i-k].c=i-k;
	}
	sort(y,y+(n-k),cmp3);
	sort(z,z+(n-k),cmp2);
	memset(vis,0,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 fff=q.top();
			if(z[b].b+fff<=y[a].a){
				my+=z[b].b+fff;
				if(my>m)
					break;
				ans++;
				q.pop();
				q.push(z[b].a-z[b].b);
				vis[z[b].c]=1;
			}else{
				my+=y[a].a;
				if(my>m)
					break;
				ans++;
				vis[y[a].c]=1;
			}
		}else{
			my+=y[a].a;
			if(my>m)
				break;
			ans++;
			vis[y[a].c]=1;
		}
	}
	cout<<ans<<endl;
	return 0;
}

 代码注解

变量及数组

n,m,k;//题目中含义
q;//存储优惠价与原价的差价的结构体优先队列
my;//储存已用了的钱数
vis[i]//标记数组
x[i],x[i].a,x[i].b;//第一部分贪心排序数组,原价,优惠价
y[i],z[i]//第二部分排序规则数组
y[i].a,y[i].b,y[i].c//同z数组,分别指原价,优惠价,编号
a,b;//在二部分中指枚举到的两块糖果

难点代码注解

bool operator()(const int &t1,const int &t2){  
        return t1>t2; 
}
//结构体内嵌比较函数,普通模板为:<返回类型说明符> operator <运算符符号>(<参数表>){<函数体>}
//注意:在过程中因为t1,t2均为常量const,所以值并不会改变
//写这个是为了把优先队列的模式改成从大到小

y[i-k];y+(n-k);
//这两段代码是为了把以n为代表的下标改成以剩下糖果总量为代表的下标