CF335F Buy One , Get One Free

题意

\(n\) 个物品 , 价格为 \(a_i\) , 每买一个物品 \(i\) 可以免费得到一个 \(a_j<a_i\) 的物品 \(j\) , 问获取所有物品的最小花费 .

\(n\le 5\times 10^5\) , \(1\le a_i \le 10^9\) .

题解

有一个最直接显然的贪心是买最大 , 送次大 , 以此类推 . 这在最大和次大不相等时是正确的 .

然而 , 题目要求送的价值严格小于买的 , 因此会出现很多价格一样的物品都必须要买 , 这样会导致答案不优 .

因此可能会出现买了若干个较大的物品 , 然后用这些机会送若干个价值相同的物品 , 考虑从大到小 , 每次加所有相同价值的物品 , 用反悔贪心来维护 . 目标是最大化送的物品总价值 , 优先反悔较小的物品 , 用小根堆维护这些物品.

考虑原来有价值为 \(x\) 的物品是送的 , 现在加的物品价值为 \(y\) , 本来 \(x\) 消耗的免费机会空了出来 , 而且买 \(x\) 还会再增加一次机会 , 因此可以免费送 \(2\) 个 \(y\) . 只要 \(2y>x\) 反悔就是优的 .

但是显然这次反悔不一定最优 , 会出现 "反悔刚才的反悔" 的情况 . 考虑反悔上述操作 , 新加的物品价值是 \(z\) , 反悔后 \(x\) 和最初一样 , 免费送 , 而两个 \(y\) 都直接买 , 产生两次机会免费送 \(z\) .

这个形式和第一次反悔相仿 , 考虑把这个操作抽象成物品放进堆里 . 最初堆中是 \(x\) , 反悔一次后总价值是 \(2y\) , 反悔两次后总价值是 \(x+2z\) , 可以理解为用一个抽象物品退出堆 , 加入 \(2\) 个 \(z\) , 又还原了 \(x\) , 这个物品的价值就是 \(2y-x\) , 而 \(x\) 一开始就不退出堆 , 因为 \(2y-x\) 肯定先考虑到 , 所有正确性没有问题 .

以上只是大体分析 , 加入抽象物品后情况会变复杂 , 在此基础上讨论具体过程和正确性 .

考虑当前是 \(z\) , 每次从堆中取出最小物品 , 它有可能是一个确定的物品 \(x\) , 有可能是一个抽象物品 \(2y-x\) .

如果是确定的 \(x\) , 肯定保证 \(x>z\) , 如果还有 \(x<2z\) , 这代表反悔 \(x\) 加入 \(2z\) 是较优的反悔 , 按照刚才的过程加入 \(2z-x\) , 相当于增广一次.

如果是抽象的 \(2y-x\) , 并不保证 \(2y-x\) 与 \(z\) 的大小关系 :

• 如果 \(2y-x<z\) , 先类比成普通物品来理解 , 肯定是直接用 \(z\) 替换 \(2y-x\) 不仅省钱更多 , 还多一次免费拿 \(z\) 的机会 , 直接用 \(z\) 来替换 \(2y-x\) 就行 .

  验证正确性 , 当前堆中是 \(x\) 和 \(2y-x\) , 替换后是 \(x\) 和 \(2\) 个 \(z\) , 都是确定的物品 , 表示正常买 \(2y\) , 机会给 \(2z\) .

  相当于 \(2y-x\) 这条增广全局不优 , 直接回退了这条增广路 , 多出来的机会直接用来往后选 .

• 如果 \(z<2y-x<2z\) , 类比成普通物品 , 应该进行一次反悔 .

  验证正确性 , 当前堆中是 \(x\) 和 \(2y-x\) , 反悔后是 \(x\) , \(2y-x\) , \(2z-2y+x\) 注意到总价值仍然是 \(x+2z\) .

  相当于 \(2y-x\) 这条增广当前不优 , 新生成的增广路退掉了它的流 , 但是如果新增广路被退流就还原这条增广路 .

进一步 , 递归产生的抽象物品都可以归纳证明 , 是可以用相同的办法处理的 .

从增广路的角度去理解 \(2y-x\) , 可以理解为要最大化免费拿的价值 , 就找当前增广路退流的最小代价. 当 \(x>y\) 时 , 有 \(2y-x<y\) , 退流的最小代价是 \(2y-x\) , 当 \(x<y\) 时 , 有 \(y<2y-x\) , 退流的最小代价是 \(y\) .

不管是确定物品还是抽象物品 , 都可以理解成一条增广路 .

#include<bits/stdc++.h>
#define file(x) freopen(#x ".in","r",stdin),freopen(#x ".out","w",stdout)
#define ll long long
#define INF 0x7fffffff
#define INF64 1e18
using namespace std;

constexpr int N=5e5+5;

ll n,a[N];

pair<ll,ll> b[N];

int m;

priority_queue<ll ,vector<ll > ,greater<ll > > q;

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	sort(a+1,a+n+1,[](int x,int y){return x>y;});
	ll res=0;
	for(int i=1;i<=n;i++){
		if(b[m].first!=a[i]){
			b[++m].first=a[i];
		}
		b[m].second++;
		res+=a[i];
	}
	ll now=0,sum=0;
	for(int i=1;i<=m;i++){
		auto [val,cnt]=b[i];
		now=min(sum-2*(ll)q.size(),cnt);
		vector<ll> tmp;tmp.clear();
		for(int j=1;j<=now;j++) tmp.push_back(val);
		ll lim=min(cnt,sum)-now;
		for(int j=1;j<=lim;j+=2){
			ll x=q.top();q.pop();
			if(x<val){
				tmp.push_back(val);
				if(j!=lim) tmp.push_back(val);
			}
			else{
				tmp.push_back(x);
				if(j!=lim&&2*val>=x) tmp.push_back(val*2-x);
			}
		}
		for(auto x:tmp) q.push(x);
		sum+=cnt;
	}
	while(q.size()) res-=q.top(),q.pop();
	cout<<res;
}

总结

这是一道很有难度的反悔贪心 . 难度有三 , 一是反悔分析涉及到递归 , 二是元素多的时候情况比较复杂 , 三是这个问题没法直接用费用流模型描述 .

关于模拟费用流和反悔贪心的关系 , 在很多简单题目中 , 这两种 "算法" 可以说是等价的 , 但是在这道题上显然地不能简单地认为等价 . 反悔贪心更接近思想 , 而费用流更接近在这个思想基础上建立的模型 , 并且有其局限性 .

换个角度说 , 费用流的底层逻辑是 "增广路" , 而 "增广路" 解决的是反悔决策递归的问题 , 而且用图论的形式严谨地描述了出来 . 对于这道题 , 图论模型描述起来较难 , 主要采取的是增广路的思想 .

简单的反悔贪心题常常增广路只会退最简单的形式的流 , 所以可以简单地解决 .

而较难的反悔贪心常常引入将反悔决策 "包装" 成某种 "抽象元素" , 并且发现和原来的元素可以同等地处理 . 其本质其实是维护了所有增广路 , 初始的增广路往往有明确的实际意义 , 伴随着反悔退流会产生更加复杂的增广路 , 它们的实际意义其实是若干个退流和推流的组合 , 因此本质上都是增广路 , 所以可以和初始增广路一样处理 .