可撤销贪心

概念

可撤销贪心一般是在一轮贪心后，在删除原来的数之后，再加入一个数，如果要选这个数，就要算上撤销一轮操作的代价（这个代价可能为负）。

经典例题

种树
- 题目大意：圆形广场共有 N 个种树的位置，顺时针编号1到N。并且每个位置都有一个美观度 (a_i) ，两株树不能种在相邻的位置（1号和N号也算相邻位置）一共有 M 株树，现在小D也想知道应该如何摆这 N 株树才能使美观度最大。
我们可以贪心，每一次从剩下可选的数中选出一个最大的 (a_i)，但这样显然是错的，因为我们可能选择(a_{i-1}) 和 (a_{i+1}) 会更优。那么怎么办呢？我们可以考虑让贪心变得可撤销。
- 假设当前我们选了第i个数，那么它的贡献就是 (a_i) 。但是最优解有可能不选它，如果不选它的话，那么就会选它的两侧相邻的点，如果这样选的话贡献就是 (a_{i-1}+a_{i+1}) 。要把之前的贪心撤消了，就相当于把ans加上 (a_{i-1}+a_{i+1}-a_i) 。新加的点其相邻关系也发生了变化，所有我们要用两个数组来记录点的相邻关系，具体操作见下。
操作步骤：
1. 用一个大根堆维护节点的观赏度。
2. 取出堆顶((i,A_i)) ，同时把i相邻的两个位置种树的价值-(A_i) 作为一个新的点加入堆，同时更新新点的左右相邻点坐标。
  - (A_i) 有可能表示种一棵树的观赏度，也有可能是种多棵树的观赏度，主要跟合并次数有关。
  - 新产生的节点减去(A_i) 是为了撤销已经在前面选了(A_i) 的决定。
  - 新产生的点必须要在节点i的两边都种上树，因为新点包含了撤销了一次的操作，可以认为在当次的操作中选了一个以前未种树的地方种树，同时把和它相邻的已经种的树挪到了另一边未种树的地方。
  - 新添加的点的相邻关系发生了变化，此时要更新新点的相邻关系。
  - 取出堆顶，说明选择了在堆顶种树，那相邻的两个点就不能种树了，所以要对相邻点进行标记。
3. 重复操作2直到M棵树均种完。

Code

#include <bits/stdc++.h>
const int maxn=2e5+5;
struct Node{
    int id,w;
    Node(){};
    Node(int x,int y){id=x;w=y;}
    bool operator <(const Node &a)const{
        return w<a.w;//大根堆
    } 
};
int L[maxn],R[maxn],flag[maxn],a[maxn],n,m,ans=0;
std::priority_queue <Node> q;
void Solve(){
    scanf("%d%d",&n,&m);
    if(n<m*2){//显然
        printf("Error!
");return;
    }
    for(int i=0;i<n;++i){//小标0~n-1,便于处理环形
        scanf("%d",&a[i]);
        q.push(Node(i,a[i]));
        L[i]=(i-1+n)%n;//i的左邻，加n是避免-1，0的左邻是n-1
        R[i]=(i+1)%n;//i的右邻n-1的右邻为0
    }
    for(int i=1;i<=m;++i){//种m棵树
        Node t=q.top(); q.pop();
        int j=t.id;
        if(flag[j]){//如果j的邻居已经种了树了
            --i; continue; //此次操作并没有种树所以--i
        }
        ans+=t.w;//选择在j处种树
        flag[L[j]]=1; flag[R[j]]=1;//把j的邻居标记上，不能种树
        a[j]=a[L[j]]+a[R[j]]-t.w;//产生新点，j两边种树，j就不能种树
        q.push(Node(j,a[j]));//新点进堆
        R[L[L[j]]]=j; L[R[R[j]]]=j;//更新新点的左右邻居和j的关系  
        L[j]=L[L[j]]; R[j]=R[R[j]];//更新新点j的左右邻居
    }
    printf("%d
",ans);
}
int main(){
   Solve();
   return 0;
}