【算法】反悔贪心总结

63 阅读 0 评论 42 点赞

我是靠谱客的博主畅快过客，最近开发中收集的这篇文章主要介绍【算法】反悔贪心总结，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

反悔问题

贪心不能反悔，因为贪心是全局最优解。

但是我们可以在贪心的条件上加上反悔的操作。

如果这一步的贪心不是最优解，我们就退回去一步，重新换一种贪心策略。

反悔自动机

设计一种反悔策略，使得随便一种贪心策略都可以得到正解。

基本的设计思路是：每次选择直观上最接近全局最优解的贪心策略，若发现最优解不对，就想办法自动支持反悔策略。

CF865D Buy Low Sell High

已知接下来N天的股票价格,每天你可以买进一股股票,卖出一股股票,或者什么也不做.N天之后你拥有的股票应为0,当然,希望这N天内能够赚足够多的钱。

分析：

这是一个非常经典、实用的问题。我们要考虑的是挑哪个时间段销售股票的权值最大，同时在这个区间内有三种操作。

我们可以想到一种策略：我们可以买入最低价格的股票，然后在可以赚钱的天数卖出去。

但是上述肯定是错误的。这样可以保证赚钱，但是无法保证赚的钱最多。

我们考虑设计一种反悔策略，使所有的贪心情况都可以得到全局最优解。

设 $S_{Buy}$ 为全局最优解中买入当天的价格， $S_{Sell}$ 为全局最优解中卖出当天的股票的价格， $S_i$ 为第 $i$ 天的股票价格

则可以列出式子： $S_{sell}-S_{buy} = (S_{sell}-S_{i})+(S_i-S_{buy})$ 这个就是反悔自动机。

我们用最少的价格去买价格最多的股票。

我们先把当前的价格放入小根堆一次，判断当前的价格是否比堆顶大，若是比其大，我们就将差值计入全局最优解，再将当前的价格放入小根堆。

相当于我们把当前的股票价格若不是最优解，就没有用。

最后可以得到全局最优解。

priority_queue<int , vector<int> , greater<int> > que;
int main(){
	cin >> n;
	ans = 0;
	for(int i = 1 ;i <= n ; i++){
		cin >>x;
		que.push(x);
		if(!que.empty() && que.top() < x){  //股票不是最优解 
			ans = ans + x - que.top(); 
			que.pop();    //最小的价格 
			que.push(x);  //反悔 
		} 
	}
	cout << ans << endl;
}

反悔堆

通过堆来维护当前贪心策略的最优解，若发现最优解不对，就退回上一步，更新最优解。

由于堆的性质，使得堆的首数据一定是最优的，这就可以实现快速更新最优解。

[USACO09OPEN]Work Scheduling G

有 $n$ 项工作，每主项工作有一个截止时间 $D_i$ ，完成每项工作可以得到利润 $P_i$ ，求最大可以得到多少利润。

分析：第一眼想到的就是：“按照截止时间为第一关键字，利润为第二关键字排序，统计一遍”。

但是啊哦，只能40pts

为什么？因为可以暂时等待一下，这回合先不拿，下回合再拿更多的钱，这样利润就更大。

如果这一步的贪心不是最优解，我们就退回去一步，重新换一种贪心策略。

假如即没有超出截止时间就分成两种情况：若当前的最优解比原来的最优解（堆顶）更优秀，我们就更新全局最优解，把原来的最优解丢出去，再把当前的最优解放进去；反之，就不管了。

假如不满足特设条件，就把当前的最优解丢进堆里，更新全局最优解即可。

#include<bits/stdc++.h>
using namespace std;
struct node{
	int Time;
	int Money;
}a[10000001];
int n;
long long ans;
priority_queue<int,vector<int>,greater<int> > q;
bool cmp(node a,node b){
	return a.Time < b.Time;
}
int main(){
	scanf("%d",&n);
	for (int i=1; i <= n; i ++) scanf("%d%d",&a[i].Time,&a[i].Money);
	sort(a + 1 , a + n + 1 , cmp);
	for (int i=1; i <= n; i++){
		if (a[i].Time <= q.size()){
			if (a[i].Money > q.top()){
				ans = ans - q.top();
				q.pop();
				q.push(a[i].Money);
				ans = ans + a[i].Money;
			}
		}
		else{
			q.push(a[i].Money);
			ans += a[i].Money;
		}
	}
	printf("%lld",ans);
	return 0;
}