反悔贪心学习笔记

· · 算法·理论

定义：

反悔贪心，顾名思义，就是可以反悔的贪心

在最初接触贪心的时候，贪心有一个重要的原则就是：无后效性原则（与DP类似）

也就是说，我们在贪心的时候，每一步做出的抉择是不能影响后续的抉择的。如果当前的抉择会影响后续操作，我们有两种方案：一是直接去使用DP求解（DP可以通过设计更多的状态来抵消后效性），另外一种就是去设计一种贪心策略，让每一步的贪心抉择都是正解

显然这两种方法都会大幅度提高求解的难度，我们考虑：是否可以通过某种操作，来抵消掉之前的选择，从而解锁之前不能进行的选择？

添加这样的操作的机制，就是反悔贪心的核心思想

反悔贪心就是给我们创造了一个机会，去修改之前的选择，从而改变自己的贪心策略，在后面及时纠正之前错误的贪心选择

也就是说反悔操作的前提为：当前的抉择获得的是局部最优解，而并非全局最优解（是不是类似于DP）。我们反悔就是为了把所有的抉择都修改为全局最优解

分类：

1.反悔堆

反悔堆就是构建一个堆来维护当前已经做出的抉择（即维护当前的最优解），如果发现最优解不优，返回上一步，手动修改最优解

由于大根堆/小根堆的性质，一般堆顶元素为最优解

2.反悔自动机

与反悔堆不同，反悔自动机没有固定的模板。简单来说，反悔自动机可以将任意一种贪心策略纠正为正解

基本的设计思路是：每次选择直观最优解，当发现最优解不优时，通过一些手段来自动支持反悔策略

一般来讲，我们通常会通过差值达到目的

例题：

1.工作调度（反悔堆）

思路：很显然的一个贪心策略就是按照DDL进行排序，把DDL靠前的任务优先完成。然后我们考虑，如果DDL发生冲突了，我们应该怎么办

一个明显的反悔思路就是：寻找当前已选任务里价值最小的那一个，如果价值小于当前事件的价值，我们就放弃之前的那件事，选择去做当前的这件事，反之则抛弃当前的事

我们可以维护一个小根堆，存储我们已经选择的事件的价值，每次和堆顶元素比较决定是否需要进行替换即可

（当时我还口胡了一个常规贪心的思路：排好序后倒着扫一遍，据说是正确的，然而并，没有尝试实现）

2.Buy Low Sell High（反悔自动机）

对于这道题，有个比较明显的等式是这样的：

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

由此我们可以构造这样的一个差值进行反悔操作：

对于任意一个股票，我们可以先入手它。当我们发现已选择的股票内有可以抛售的，我们就抛售它，然后再次入手它作为反悔

核心代码如下：

for(int i=1;i<=n;++i)
{
    q.push(num[i]);
    if(q.size()&&q.top()<num[i])
    {
        ans+=num[i]-q.top();
        q.pop();
        q.push(num[i]);
    }
}

3.种树（反悔自动机）

这个题也是敦促我学习反悔贪心的动力源

相较于前面的两道题，这道题更好地诠释了反悔自动机的差值机制

由于相邻的树是冲突的，因此当我们选择了一棵树，它对应的反悔差值就是不选当前的这棵树，选择它左右两边的树

每一次选择一棵树时，我们可以构建一个不存在的树坑，让它的价值为当前树坑左右两个树坑的价值之和减去当前树坑的价值

对于这个虚构的树坑，因为它相当于是相邻的三个树坑捆绑得到的结果，因此它的左边是当前树坑左边的左边的树坑，右边同理

对于这个，我们可以用双向链表来进行维护（当然是数组模拟的）。同时也不要忘记对于选择的树坑，给它的左右树坑打上标记。当我们遇到被标记的树坑，直接跳过就好了

核心代码如下：

for(int i=1;i<=m;++i)
{
    while(vis[q.top().id])q.pop();
    ans+=q.top().w;
    int cid=q.top().id,cw=q.top().w;
    q.pop();
    nxt.id=++tot;
    w[tot]=w[l[cid]]+w[r[cid]]-cw;
    nxt.w=w[tot];
    l[r[r[cid]]]=tot;r[l[l[cid]]]=tot;
    l[tot]=l[l[cid]];r[tot]=r[r[cid]];
    vis[l[cid]]=1;vis[r[cid]]=1;
    q.push(nxt);
}