反悔贪心

· · 个人记录

简介

当贪心策略失效时，可以考虑反悔得到全局最优解，反悔一般用堆实现。

对于一些普通反悔贪心，堆中的元素很容易想到。复杂一些的问题中，我们考虑在 朴素贪心每次确定决策 时再加入一些修正值，以此达到反悔的效果。

关键就是反悔操作的设计以及修正值取啥了，我们可以这样考虑：

C_{i,j}+C_{j2,k}=C_{i,k}

其中，C_{i,j} 表示朴素贪心策略中，决策 (i,j) 的贡献值，为了得到全局最优解，即考虑到更优的决策 (i,k)，我们可以再将修正值 j2 加入堆中，那么满足上述式子就可视作反悔了。

（有差分那味儿了）

例题 CF865D

显然有朴素贪心策略：对于 a_i，回头找到 \min a_j 然后交易。

那么会被 a_i<a_j<a_k 的情形卡掉，上述策略的答案是 a_j-a_i 而正确答案是 a_k-a_i。

这就很符合反悔贪心的核心式子。

首先有 C(i,j)=a_j-a_i，那么带入得：

a_j-a_i+k-j2=a_k-a_i

化简后就有 j2=a_j，于是乎就解决了。

有些细节和不解还是要自己思考思考的。

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

#define int long long
int n,a,ans;
priority_queue<int,vector<int>,greater<int> >q;

signed main() {
    cin>>n;
    for(int i=1; i<=n;i++){
        scanf("%lld",&a);
        if(!q.empty()&&q.top()<a){
            ans+=a-q.top(); //计算贡献
            q.pop(); 
             q.push(a); //反悔
        }
        q.push(a); 
        //注意到ai除了被当作修正值外，自己还可以被买入，所以还要入一次队
    }
    cout<<ans;
    return 0;
}

例题 P1792 [国家集训队] 种树

朴素贪心：将所有点的价值加入大根堆，每次取最大值并标记其两边的点。

错误原因：显然，我们不一定要取这个点，有时取两边的点反而更优。

设当前点为 k，那么考虑一种反悔操作，使得撤销选 k 这个操作，并计算两侧点的贡献。

易想到：重新在队列中加入一个价值为 a_{left}+a_{right}-a_k 的点便能起到反悔的效果。

不过这样做还不够严谨，也许我们不一定取 left,right 而是取 left_{left},right_{right} 呢？

注意到问题的相似性，我们便有了最终思路：对于 k 的反悔操作，是将 left,k,right 这三点合并为一点，且需要维护新点的左右点，价值即为上式。

不难发现，这样做恰好包含了所有可能情形。

程序实现中，使用双向链表即可支持上述操作。

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

const int N=2e5+5;
int n,m,a[N],lt[N],rt[N],ans;
bool vis[N];
priority_queue<pair<int,int> >q;

inline void change(int u){
    vis[lt[u]]=vis[rt[u]]=true;
    a[u]=-a[u];
    if(lt[u]) a[u]+=a[lt[u]];
    if(rt[u]) a[u]+=a[rt[u]];
    lt[u]=lt[lt[u]]; rt[u]=rt[rt[u]];
    rt[lt[u]]=u; lt[rt[u]]=u;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1; i<=n;i++){
        scanf("%d",&a[i]);
        q.push({a[i],i});
    }
    for(int i=1; i<=n;i++){
        lt[i]=(i-1==0?n:i-1);
        rt[i]=(i+1==n+1?1:i+1);
    }
    if(n<(m<<1)){
        cout<<"Error!";
        return 0;
    }
    while(m&&!q.empty()){
        int val=q.top().first,xb=q.top().second;
        q.pop();
        if(vis[xb]) continue;
        --m; ans+=val;
        change(xb);
        q.push({a[xb],xb});
    }
    cout<<ans;
    return 0;
}