[学习笔记24] 反悔贪心

Imaginative · 2025-09-25 02:11:14 · 个人记录

知识点

反悔贪心

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

反悔堆

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

由于堆的性质，堆的首数据一定是最优的，这就可以实现快速更新最优解（通过例题来理解）

反悔自动机

即设计一种反悔策略，使得任意一种贪心的策略都能保证全局最优解

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

具体题目具体分析。一般需要反悔自动机的题都是通过差值巧妙达到反悔的目的。 ——by~@nth_element

例题

A.P2949 Work Scheduling G

题目链接

简化题意:你有 1e9 个时刻，有 n 项工作，每份工作有截止时间 D_i 和利润 P_i ，规定每项任务完成时间是 1 问你最大能获得多少利润。

因为有个时间限制，我们很难想到直接写出 dp 式子，考虑贪心。有两种最直接的贪心:

先做截止时间早的
先做利润大的

很明显两种都不一定优。

对于贪心策略1，如果截止时间早的利润特别小，截止时间玩的利润特别大，且做了小利润任务就做不了大利润任务。
对于贪心策略2，如果利润大的截止时间晚，利润小的截止时间早。我们选择利润大的抛弃了利润小的，但是可能我们可以两者皆取，先做利润小的再做利润大的，故此时也不优。

对于改进贪心策略，我们有两种方式。

第一种：我们注意到第二次贪心错误是因为考虑完价值之后没有考虑时间，那么我们可以让每次选取价值大的任务每次压线做完，空出前方做多的时间给尽可能多的任务，那么此时的贪心既考虑了时间有考虑了价值便是正确的。直接做是O(n^2)的，找空位的时候用树状数组优化，时间可以到 O(nlogn)

第二种：反悔贪心，这种优化的是第一种贪心。注意到第二种贪心的错误是漏选而第一次是错选，那么我们可以通过反悔改正。因为每个任务花费时间都是1，如果有一个任务它截止时间比你晚，价值还比你大，并且你又是所有已做任务中价值最小的，那么很显然此时最优解应该是将做这个任务的时间改为做更优任务。

大/小根堆用 priority_queue 写就行

B.建筑抢修

将上题的价值全部换为了1，但是每个任务有了完成时间 t_i ,在截止时间前(包括截止时刻)没有做完，那任务就废了。

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

C.Job Completion G

与上题基本一致，但是将规则改为在截止时间(包括截止时刻)没有做(不是做完)任务才废。

这里要考虑怎么进行最优性排序。两种思考；

感性理解，如果我们在开始截止时刻才做，做完那一刻就是结束截止时刻，此时便与B题一致。
理性分析，如果我们先选了先任务i可以选任务j ,但反之不行，设选两任务之前时间为 T ,则有： T+t_i<=s_j~~~~->~~~~T<=s_j-t_i T+t_j>s_i~~~~->~~~~T>s_i-t_j
联立两式
s_i-t_j<s_j-t_i~~~~->~~~~s_i+t_i<s_j+t_j
因此便是按照 s_i+t_i 为关键字排序即可,随后反悔贪心。

D.Buy Low Sell High

简要题意：已知接下来 n 天的股票价格，每天可以买入当天的股票，卖出已有的股票，或者什么都不做，求 n 天之后最大的利润。

最直接的贪心，对于每个 i ,如果可以卖出股票，那么要在上一次卖出那天到第 i 天中间找一个价格最小的(满足价格小于第i天)买入。

显然具有缺陷，因为可能后面那天买入比今天更优，考虑优化。这里要思考什么时候要去反悔，要反悔之前的什么。这时就需要思考一种反悔策略，使得所有贪心情况都可以转为全局最优解。(即反悔自动机)

设 C_{buy} 为全局最优解中买入当天的价格，C_{sell} 为全局最优解中卖出当天的价格，则：

C_{sell} - C_{buy} = (C_{sell} -C_i) + (C_i - C_{buy})

比如 10,12,20 这一组我们想要的是 C_3-C_1 但求出来 C_2-C_1 ,改正就是：

C_3-C_1=(C_3-C_2)-(C_2-C_1)

那么贪心思路就很明显了，对于一个卖错了的我们直接买回去再卖，时间复杂度 O(nlogn)

代码 by zythonc

#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.序幕

题意：有 n 块点心，第 i 块点心的美味度为 a_i 。你不能吃连续的两块点心。你想知道对于每个 i∈[1,⌈n/2⌉] ，吃 i 块点心的美味度之和的最大值。

(懒得写了，贴一下官方的题解和我改了3-4天的代码)

反悔贪心。设选的为1，不选为 0。考虑进行一些选择后的物品序列一定形如若干 1010…0101。彼此之间是一些 0。

接下来用 [l,r] 表示 [l,r] 的选择方案为 1010…0101。维护一个大根堆，里面是所有可能下次选择的 [l,r]，每次取出堆顶，标注 l、r 为已考虑，并往堆中加入反悔操作 [l−1,r+1]。如果 l、r 已经被标注已考虑就不停取堆顶，直到取到合法 [l,r]。可以发现，每次贡献递减，本质是费用流的增广过程。时间复杂度 O(nlogn)

可以用双向链表反悔自动机写，这里需要注意，如果 l-1 和 r+1 都已经被考虑也可以直接弹出了。

#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
*/