专栏文章

[学习笔记24] 反悔贪心

IImaginative
个人记录参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minsqym6
此快照首次捕获于
2025/12/02 07:45
3 个月前
此快照最后确认于
2025/12/02 07:45
3 个月前
查看原文

知识点

反悔贪心

  • 反悔贪心是基于普通贪心的一种优化，它的核心思想是：在贪心选择后，若发现当前解并非全局最优，则通过调整策略或撤销操作来获取更优解，同时保证一个优的复杂度。按照判断方式的不同可以分为反悔自动机和反悔堆两种方法。而 dpdp 虽然保证正确性，但时间开销却相对较多。
  • 基于反悔的特性，一定程度上保证了贪心的局部最优解接近于全局最优解，但很显然它并不总是正确。但是这仍然提供给我们一个思路，如果在做一道题时，发现贪心错误， dpdp 不会优化，可以试试反悔贪心能不能写。

反悔堆

即通过堆来维护当前贪心策略的最优解，若发现最优解不对，就退回上一步，更新最优解。
由于堆的性质，堆的首数据一定是最优的，这就可以实现快速更新最优解（通过例题来理解）

反悔自动机

即设计一种反悔策略，使得任意一种贪心的策略都能保证全局最优解
其设计思路是：每次选择最接近全局最优解的贪心策略，若发现不对，就想办法自动支持反悔策略。
具体题目具体分析。一般需要反悔自动机的题都是通过差值巧妙达到反悔的目的。 ——by @nthby~@nth_elementelement

例题

A.P2949 Work Scheduling G

题目链接
简化题意:你有 1e91e9 个时刻，有 nn 项工作，每份工作有截止时间 DiD_i 和利润 PiP_i ，规定每项任务完成时间是 11 问你最大能获得多少利润。
因为有个时间限制，我们很难想到直接写出 dpdp 式子，考虑贪心。有两种最直接的贪心:
  1. 先做截止时间早的
  2. 先做利润大的
很明显两种都不一定优。
  • 对于贪心策略1，如果截止时间早的利润特别小，截止时间玩的利润特别大，且做了小利润任务就做不了大利润任务。
  • 对于贪心策略2，如果利润大的截止时间晚，利润小的截止时间早。我们选择利润大的抛弃了利润小的，但是可能我们可以两者皆取，先做利润小的再做利润大的，故此时也不优。
对于改进贪心策略，我们有两种方式。
第一种：我们注意到第二次贪心错误是因为考虑完价值之后没有考虑时间，那么我们可以让每次选取价值大的任务每次压线做完，空出前方做多的时间给尽可能多的任务，那么此时的贪心既考虑了时间有考虑了价值便是正确的。直接做是O(n2)O(n^2)的，找空位的时候用树状数组优化，时间可以到 O(nlogn)O(nlogn)
第二种：反悔贪心，这种优化的是第一种贪心。注意到第二种贪心的错误是漏选而第一次是错选，那么我们可以通过反悔改正。因为每个任务花费时间都是1，如果有一个任务它截止时间比你晚，价值还比你大，并且你又是所有已做任务中价值最小的，那么很显然此时最优解应该是将做这个任务的时间改为做更优任务。
大/小根堆用 prioritypriority_queuequeue 写就行

B.建筑抢修

将上题的价值全部换为了1，但是每个任务有了完成时间 tit_i ,在截止时间前(包括截止时刻)没有做完，那任务就废了。
显然第一种优化贪心已经不适用，因为价值均为1。考虑第二种，我们依旧按截止时间先后去做。如果能做就做，遇到不能做的任务时，如果这个任务占用时间比已做时间最大的晚，很显然我们可以放弃已做的那个换取占用时间少的，这样可以腾出更多空间给后来的，且这样总价值不变。如果这个任务比已选的所有都要大，那么换成它一定变劣。

C.Job Completion G

与上题基本一致，但是将规则改为在截止时间(包括截止时刻)没有做(不是做完)任务才废。
这里要考虑怎么进行最优性排序。两种思考；
  1. 感性理解，如果我们在开始截止时刻才做，做完那一刻就是结束截止时刻，此时便与B题一致。
  2. 理性分析，如果我们先选了先任务ii可以选任务jj ,但反之不行，设选两任务之前时间为 TT ,则有： T+ti<=sj    −>    T<=sj−tiT+t_i<=s_j~~~~->~~~~T<=s_j-t_i T+tj>si    −>    T>si−tjT+t_j>s_i~~~~->~~~~T>s_i-t_j 联立两式 si−tj<sj−ti    −>    si+ti<sj+tjs_i-t_j<s_j-t_i~~~~->~~~~s_i+t_i<s_j+t_j 因此便是按照 si+tis_i+t_i 为关键字排序即可,随后反悔贪心。

D.Buy Low Sell High

简要题意：已知接下来 nn 天的股票价格，每天可以买入当天的股票，卖出已有的股票，或者什么都不做，求 nn 天之后最大的利润。
最直接的贪心，对于每个 ii ,如果可以卖出股票，那么要在上一次卖出那天到第 ii 天中间找一个价格最小的(满足价格小于第ii天)买入。
显然具有缺陷，因为可能后面那天买入比今天更优，考虑优化。这里要思考什么时候要去反悔，要反悔之前的什么。这时就需要思考一种反悔策略，使得所有贪心情况都可以转为全局最优解。(即反悔自动机)
设 CbuyC_{buy} 为全局最优解中买入当天的价格，CsellC_{sell} 为全局最优解中卖出当天的价格，则：
Csell−Cbuy=(Csell−Ci)+(Ci−Cbuy)C_{sell} - C_{buy} = (C_{sell} -C_i) + (C_i - C_{buy})
比如 10,12,2010,12,20 这一组我们想要的是 C3−C1C_3-C_1 但求出来 C2−C1C_2-C_1 ,改正就是： C3−C1=(C3−C2)−(C2−C1)C_3-C_1=(C_3-C_2)-(C_2-C_1) 那么贪心思路就很明显了，对于一个卖错了的我们直接买回去再卖，时间复杂度 O(nlogn)O(nlogn)
代码 by zythonc
CPP
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,in[1000001],ans;
priority_queue<int,vector<int>,greater<int> >q;
signed main(){
	cin>>n;
	for(int i=1;i<=n;i++) cin>>in[i];
	for(int i=1;i<=n;i++){
		q.push(in[i]);
		if(in[i]>q.top()){
			ans+=in[i]-q.top();
			q.pop();
			q.push(in[i]);
		}
	}
	cout<<ans;
}
代码的意思就是每一次遇到一个股票就买，但后面出现了一个比它大的才贡献答案。push两遍是因为这个点可能会被后来反悔而不被选，那么此时它后面有更大的就可以重新选这个点。

E.序幕

题意：有 nn 块点心，第 ii 块点心的美味度为 aia_i 。你不能吃连续的两块点心。你想知道对于每个 i∈[1,⌈n/2⌉]i∈[1,⌈n/2⌉] ，吃 ii 块点心的美味度之和的最大值。
(懒得写了，贴一下官方的题解和我改了3-4天的代码)
反悔贪心。 设选的为1，不选为 0。考虑进行一些选择后的物品序列一定形如若干 1010…0101。彼此之间是一些 0。
接下来用 [l,r][l,r] 表示 [l,r][l,r] 的选择方案为 1010…01011010…0101。维护一个大根堆，里面是所有可能下次选择的 [l,r][l,r]，每次取出堆顶，标注 l、rl、r 为已考虑，并往堆中加入反悔操作 [l−1,r+1][l−1,r+1]。如果 l、rl、r 已经被标注已考虑就不停取堆顶，直到取到合法 [l,r][l,r]。 可以发现，每次贡献递减，本质是费用流的增广过程。 时间复杂度 O(nlogn)O(nlogn)
可以用双向链表反悔自动机写，这里需要注意，如果 l−1l-1 和 r+1r+1 都已经被考虑也可以直接弹出了。
CPP
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
#define int long long
int n;
struct node{
	int val,id;
	friend bool operator<(node x,node y){
		return x.val>y.val;
	}
}a[N];
int ans[N],cnt,vis[N],tot;
struct que{
	int l,r,val;
	friend bool operator<(que x,que y){
		return x.val<y.val;
	}
};
int res=0;
priority_queue<que>q;
int flag[N];
int tol[N],tor[N];
int qz1[N],qz2[N];
signed main(){
	freopen("starter.in","r",stdin);
	freopen("starter.out","w",stdout);
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i].val,a[i].id=i,q.push(que{a[i].id,a[i].id,a[i].val});;
	qz1[1]=a[1].val;
	for(int i=3;i<=n;i+=2) qz1[i]=qz1[i-2]+a[i].val;
	for(int i=2;i<=n;i+=2) qz2[i]=qz2[i-2]+a[i].val;
	for(int i=1;i<=n;i++) tol[i]=tor[i]=i;
	int cnt=0;
	while(q.size()&&cnt<ceil(n*1.0/2)){
		while(tol[q.top().r]!=q.top().l||tor[q.top().l]!=q.top().r||vis[q.top().l-1]||vis[q.top().r+1]) q.pop();
		que k=q.top();
		//if(k.l<1) k.l=0;
		//else if(k.r>n) k.r=n+1;
		//if(k.val==0) cout<<k.l<<" "<<k.r<<"\n";
		q.pop();
		cnt++,res+=k.val;
		vis[k.l]=vis[k.r]=1;
		int L,R;
		if(tol[k.l-1]&&tor[k.r+1]){
			L=tol[k.l-1],R=tor[k.r+1];
			tor[tol[k.l-1]]=tor[k.r+1];
			tol[tor[k.r+1]]=tol[k.l-1];
		}
		else if(tol[k.l-1]&&!tor[k.r+1]){
			L=tol[k.l-1],R=k.r+1;
			tor[tol[k.l-1]]=k.r+1;
			tol[k.r+1]=tol[k.l-1];
		}
		else if(!tol[k.l-1]&&tor[k.r+1]){
			//if(k.l==k.r&&k.l==2) cout<<tor[3]<<" "<<tol[5]<<"\n";
			L=k.l-1,R=tor[k.r+1];
			tor[k.l-1]=tor[k.r+1];
			tol[tor[k.r+1]]=k.l-1;
		}
		else{
			L=k.l-1,R=k.r+1;
			tor[k.l-1]=k.r+1,tol[k.r+1]=k.l-1;
		}
		if(L%2) q.push(que{L,R,qz1[R]-qz1[L-2]-(qz2[R-1]-qz2[L-1])});
		else q.push(que{L,R,qz2[R]-qz2[L-2]-(qz1[R-1]-qz1[L-1])});
		ans[cnt]=res;
	}	
	for(int i=1;i<=ceil(n*1.0/2);i++) cout<<ans[i]<<"\n";
	return 0;
}
/*
10
6 9 5 5 9 1 2 5 6 8 
5
3 5 1 7 6
7
1 3 0 4 22 0 0
*/

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...