自动搬运

查看原文

来自洛谷，原作者为

	InfiniteHorizon AFOed | 去见想见的人吧，趁阳光正好，趁微风不噪，趁繁花还未开至荼蘼，趁现在还年轻。

搬运于2025-08-24 21:44:44，当前版本为作者最后更新于2023-07-26 18:36:42，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

这是反悔贪心的一道好题。

有人问，反悔贪心是什么？

其实贪心本身不带有反悔，是因为此时的贪心可以从局部最优解推出全局最优解。但当有些时候局部最优解推不出全局最优解时，就要用反悔贪心，在适当的时候撤销之前做出的决策。

我们先选取 $c$ 最小的 $k$ 个物品使用优惠劵，当前已经使用的价格是 $tot$。下文为方便表述，记使用优惠劵的物品集合为 $A$，他在求解过程中不是固定不变的。

当前考虑第 $i$ 个物品，由于 $k$ 张优惠券已经用完了，所以只能以原价 $p_i$ 购买物品 $i$。现在考虑反不反悔的条件是什么。

如果要反悔，那么用优惠券买 $i$ 的价格一定要小于用原价买 $i$。当 $i$ 用了优惠券，那么 $A$ 势必要有一个物品（记为 $j,j \in A$）做出退让，用原价来买 $j$。（其实相当于用 $i$ 来代替 $j$），那么一定满足以下不等式：

意思是：$i$ 代替 $j$ 用优惠券的价格比用原价买 $i$ 便宜，这个时候就需要反悔。

发现 $tot$ 可以消去：

然后把下标相同的归在小于号的同一侧：

他们的形式是相同的，所以我们可以设 $\Delta_i=p_i-c_i$：

所以只要在已经使用优惠券的物品里面，存在一个 $j$，使得 $\Delta_j<\Delta_i$，我们就需要用 $i$ 代替 $j$ 使用优惠券。也就是 $k$ 个物品中，$(\Delta_j)_{\min}<\Delta_i$ 。注意这个不是恒等式，因为 $i \notin A$，但是 $j\in A$。

最小值可以用优先队列来求。

话不多说，上代码，代码中用 $delta$ 优先队列存储了上文中提到的 $\Delta_j,j\in A$，$P$ 存储原价 $p_i$，$C$ 存储优惠价 $c_i$。

#include<bits/stdc++.h>
#define int long long
using namespace std;

const int maxn=50010;

int n,k,m;
int p[maxn],c[maxn];
bool buy[maxn];//buy[i] 表示第 i 个物品是否被买过
int ans=0;
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >P,C;
priority_queue<int,vector<int>,greater<int> >delta;

signed main(){
	cin>>n>>k>>m;
	for(int i=1;i<=n;++i){
		cin>>p[i]>>c[i];
		P.push(make_pair(p[i],i));
		C.push(make_pair(c[i],i));
	}
	for(int i=1;i<=k;++i) delta.push(0);
	while(!P.empty()){
		pair<int,int> x1=P.top();
		pair<int,int> x2=C.top();
		if(buy[x1.second]){//如果被买过了，就跳过
			P.pop();
			continue;
		}
		if(buy[x2.second]){
			C.pop();
			continue;
		}
		if(delta.top() > x1.first-x2.first){//这个式子和上文推的式子时相反的，表示用原价买 i 更划算
			m-=x1.first;
			P.pop();
			buy[x1.second]=true;
		}
		else{//否则的话，就是用优惠券买 i 更划算
			m-=x2.first+delta.top();
			delta.pop();
			C.pop();
			buy[x2.second]=true;
			delta.push(p[x2.second]-c[x2.second]);
		}
		if(m>=0) ans++;
		else break;
	}
	cout<<ans<<endl;
	return 0;
}

最后，希望大家都能真正理解返回贪心，它的精髓就是“常思己过”！

静坐常思己过，闲谈莫论人非。——明 · 罗洪先《醒世诗》