众所周知，人都是贪心的。这里的贪心和我们贪心算法的贪心是一致的，就是我们会尽量追求一个问题解决的最优解。但是在贪心算法当中，我们只是在意一个问题的局部最优解，这往往可能让我们远离最后的全局最优解。那有没有什么方法能够让我们在在贪心的过程总不断摸索不断修改得到最终的全局最优解呢？反悔贪心就是其中的一种。

什么是反悔贪心

众所周知，正常的贪心算法是指在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，算法得到的是在某种意义上的局部最优解。也就是说我们的每一步都是站在当前产生的局面上所作出的最好的选择，是没有反悔操作的。

不加反悔的一直朝着当前局面的最优解走很可能导致我们被困在局部的最优解而无法到达全局的最优解，就好像我们爬山就只爬到了一座山的山顶却没有到整片山的最高处：

但是反悔贪心允许我们在发现现在不是全局最优解的情况下回退一步或若干步采取另外的策略去取得全局最优解。就好像我们站在的一座山的山峰上，看到了还有比我们现在所在位置还高的山峰，那我们现在就肯定不是在最高的地方了，这时我们就反悔——也就是下山再爬上那座更高的山：

这就是反悔贪心的大致思路。根据反悔记录操作的不同，反悔贪心又分为反悔堆和反悔自动机，下面我们就分别来看看这两种反悔贪心的模型吧。

反悔堆

基本思路

反悔堆是反悔贪心当中比较简单的一类模型，常常被运用在简单的调度问题上。其一般是使用大根堆或者小根堆记录当前决策中最“拉跨”的部分，随着我们决策的深入，我们可以用更好的方案替换掉之前“拉跨”的部分，来获得一个更好的方案。

这样说可能有点抽象，我们可以举一个简单的例子。假如我们有一个背包，只可以放3件物品，现在我们有五件物品，其价值分别是 1，2，3，4，5。现在我们考虑怎么贪心。首先我们先把前三件物品放入背包中，这时我们背包有 【1，2，3】 三件物品。这时我们想要加入价值为4的这件物品，但是背包满了，怎么办呢？我们就看一下现在背包里最“拉跨”也就是价值最低的是多少，一看原来是 1 ，并且1 < 4。所以这时我们就直接把 1 丢弃掉把 4 塞进来。同理加入价值为 5 的物品时，我们也把这时背包(【2，3，4】)里最“拉跨”的 2 给丢掉，把 5 给拿进来，这样得到的背包就是价值最大的背包。

那我们如果快速得知这个最“拉跨”也就是价值最小的物品是多少呢？我们可以使用小根堆把背包里现有的元素丢到堆里，这样堆顶的元素就一直都是价值最小的元素啦。顺带一提，在具体的实现中，我们很少真的去手写堆，一般都是使用更加方便快捷的优先队列来完成这样的操作。

这就是反悔堆的大致思路，下面我们来看看两种反悔堆实用的经典调度问题模型——用时一定模型和价值一定模型。

用时一定模型

题目描述

我们考虑这样一个问题，我们有n个任务(n≤1e5)，每个任务都恰好需要一个单位时间完成，并且每个任务都有两个属性——截止日期和价值。在截止日期前完成任务就可以得到这个任务产生的价值。每个单位时间我们都可以选择这n个任务当中还没有做过的并且还没有截止的任务中的一个去完成，问我们最后最多能得到多少价值呢？

算法讲解

这种模型看上去非常简单，感觉就能用非常简单的贪心就能完成，实则不然，我们先来看看最容易想到的几种简单贪心为什么不行。

简单贪心尝试

第一种贪心是开一个桶，对于每一个截止日期我们都只保留能产生价值最大的任务去做，其余的不去做。这种方法很明显是错误的，我们可以举出一个例子来否定这个策略。比如我们只有两个任务A和B，A任务的截止日期是3，价值是3；B的截止日期是3，价值是1。按照我们的贪心策略，我们就舍弃B选择A，但是实际上，我们可以在时间2去做B，时间3去做A这样就可以全都要，明显比只做A会好得多，所以这种贪心策略是不可取的。

第二种贪心就更加明智一点，我们都有一种直觉那就是先完成比较紧急的任务亦或者说先完成截止日期靠前的任务会更加优。所以我们就按照截止日期(从小到大)为第一关键字，价值(从大到小)为第二关键字进行排序，然后顺序遍历每个任务，能做就做，不能做(当前已安排任务数=当前任务的截止日期)就直接抛弃。这样做看起来很有道理，但实际上有有可能到后期都是高报酬的工作（但由于前期做了太多价值很低的任务导致都超时做不了了）就会让答案不是很优秀。比如我们举个例子。加入我们有四个任务A、B、C、D.其中A任务的截止日期为1，价值为2；B的截止日期为1，价值为1；C的截止日期为2，价值为5；D的截止日期为2，价值为6。按照我们现在的贪心策略，我们会排序后按照ABDC的顺序进行考虑，然后选择AD这两个任务去完成最后结果是8。但实际上，如果我们不去做A，而是把做A的时间拿去做C，这样我们最后的结果就是11是优于我们的贪心答案的。

为什么会出现这样的问题呢？是因为到了后期，我们见到了很多高回报的工作但是能做的却很有限了，这又是因为前期做了很多价值很低的任务，换句话说我们可能会后悔前期做了些低报酬的工作。那我们能不能反悔，也就是退掉之前低报酬的工作用那个时间去完成高报酬的工作呢？这就要用到我们的反悔堆。

当然我们还有第三种贪心，以价值为关键字从大到小排序，假如我们考虑第i个任务做不做，如果从1∼t[i]（第i个任务的截止时间） 没有塞满，那就尽量咕到最后一个空位做，正确也是显然的，但是直接暴力是 O(n^2)的。然后我们发现找空位的过程可以优化，加入树状数组，二分位置判断即可，时间复杂度 O(nlog^2n)即可以通过。

反悔贪心解法

我们仔细分析一下这道题，我们发现，对于任意两个任务A和B，假设A的截止日期小于B，现在我们决定在某个时间去做A，那这个时间同样也可以不做A去做B(因为B的截止日期大于A)。有了这个结论，我们就可以使用反悔堆了。

为了运用上面这个性质，我们还是得将所有的任务按照截止时间从小到大排序。接着我们用一个按价值排序的小根堆，维护当前我们决定做的任务当中产生报酬的最小任务。

然后我们顺序遍历每一个任务，如果当前堆内元素个数也就是我们现在决定做的任务数小于现在我们考虑的这个任务的截止时间，那就代表我们还有充足的时间去完成这个任务，那我们就直接去做这个任务就好了。具体来说就是让答案加上这个任务的价值，然后把这个任务扔进小根堆里。

但如果当前的堆内元素个数大于我们现在考虑的这个个任务的截止时间，那就代表这个任务的截止时间之前的所有时间都安排满了，那我们只好看一看能不能不做之前决定做的一个任务，用这个时间去做现在这个任务。这时我们就要用到我们的小根堆了，由于小根堆堆顶任务的价值是全部决定做的任务当中最小的，我们就只需要比较堆顶任务的价值和现在考虑的这个任务的价值。

如果堆顶任务的价值大于我们当前考虑任务的价值，这就是代表着我们已选任务的价值最小的都比我们当前考虑任务的价值大，那很明显，把之前的任务换成现在考虑的任务是亏的，我们就不做操作。

但如果堆顶任务的价值小于我们当前考虑任务的价值，这就是代表着我们已选任务的价值最小值是不及我们当前考虑的这个任务的，那我们就不做堆顶的任务，用做之前那个任务的时间去做我们当前考虑的这个任务就可以啦。具体到操作上，我们就让答案减去堆顶的任务价值，再把堆顶任务从堆中移除，代表反悔——不做这个任务了，接着我们再让答案加上我们当前考虑的这个任务的价值，并把这个任务丢到堆里就可以啦。

这里需要记住的是，因为每完成一个工作需要的时间都是1，所以小根堆中节点的数量就是已经花费的时间。

这样我们就使用反悔堆完成了这个操作，这样下来时间复杂度就是堆操作的复杂度也就是O(nlogn)的。

模板代码

这道题也是有模板题的，就是 [USACO09OPEN]Work Scheduling G，下面附上模板代码：

#include <cmath> 
#include <queue>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
struct node {
    int deadline, value;
    bool operator < (const node &v) const
    {
        if(value > v.value)return(true);
        else return(false);
    }//重载<号的定义，规定堆为关于价值的小根堆 
}a[110000];
priority_queue<node>q;//用优先队列代替手写堆 
int n;
long long ans = 0;

bool comp(node x, node y) {
    if (x.deadline < y.deadline) return(true);
    else return(false); 
}//自定义排序函数，将任务按截止时间从小到大排序 
int main() {
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) scanf("%d%d", &a[i].deadline, &a[i].value);
    sort(a + 1, a + n + 1, comp);
    //读入和排序 
    for(int i = 1; i <= n; i++) {
        if(a[i].deadline > q.size()) {
            ans += a[i].value;
            q.push(a[i]);
        }//如果当前决定做的任务数小于截止日期也就是还有时间做当前任务 
        else {
            if(a[i].value > q.top().value) {//如果堆顶小于当前考虑任务的价值 
                ans -= q.top().value; q.pop();
                ans += a[i].value;
                q.push(a[i]);
            }//反悔操作 
        }//考虑是否反悔，不做之前做的任务 
    }

    printf("%lld", ans);
    return 0;
} 

价值一定模型

题目描述

我们再来考虑这样一个问题，我们有n个任务(n≤1e5)，并且每个任务都有两个属性——截止日期和完成耗时。在截止日期前完成任务就可以得到这个任务产生的价值。在同一时间我们只能去做一个任务。所有任务的价值都是一样的，问我们最后最多能完成多少个任务。

算法讲解

有了刚刚那题的基础，我们也很容易可以考虑到反悔贪心的反悔堆模型上。由于我们需要反悔操作，而反悔操作是建立我们能够反悔——不做之前决定做的任务而去做当今决定做的任务，所以首先我们肯定还是要按照截止日期从小到大进行排序。

在我们上面讲到的用时一定的模型中，我们用堆维护“性价比”最低的任务也就是我们价值最低的任务用于反悔操作。在这个问题中，我们同样用堆去维护“性价比”最低的任务。由于每个任务的价值是一定的，所以我们性价比最低的任务就是耗时最长的任务，如果我们不做耗时比较长的任务去做耗时比较短的任务，我们就能留下更多的时间给后面的任务，又由于每个任务的价值是一样的，所以这样做的正确性也是显然的。

所以具体来说我们就开一个大根堆维护已选任务的时间，堆顶就是耗时最长的任务。我们顺次考虑排序后的每个任务，当前决定要做的任务的总耗时加上现在这个任务的耗时小于等于现在这个任务的截止时间，那我们就直接做，把现在这个任务丢进堆里，总耗时加上现在这个任务的耗时就可以了。但如果当前决定要做的任务的总耗时加上现在这个任务的耗时大于现在这个任务的截止时间呢，我们就考虑是否进行反悔操作替换决定做的任务。我们看一看堆顶任务的耗时和现在这个任务的耗时，如果堆顶任务的小那就不替换；如果当前任务的耗时小，我们就用当前任务替换掉堆顶任务就好啦。

模板代码

这道题也是有模板题的，题目是[JSOI2007]建筑抢修，下面附上模板代码：

#include <cmath> 
#include <queue>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
struct node {
    int deadline, time;
    bool operator < (const node &v) const
    {
        if(time < v.time)return(true);
        else return(false);
    }//重载<号的定义，规定堆为关于耗时的大根堆 
}a[160000];
priority_queue<node>q;//用优先队列代替手写堆
int n;
long long last = 0;

bool comp(node x, node y) {
    if (x.deadline < y.deadline) return(true);
    else return(false); 
}//自定义排序函数，将任务按截止时间从小到大排序  
int main() {
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) scanf("%d%d", &a[i].time, &a[i].deadline);
    sort(a + 1, a + n + 1, comp);
    //读入和排序 
    for(int i = 1; i <= n; i++) {
        if(a[i].deadline >= last + a[i].time) {
            last += a[i].time;
            q.push(a[i]);
        }//如果决定做的任务耗总时加上当前任务耗时小于等于当前任务截止时间 
        else {
            if(a[i].time < q.top().time) {//如果堆顶耗时大于当前考虑任务的耗时 
                last -= q.top().time; q.pop();
                last += a[i].time;
                q.push(a[i]);
            }//反悔操作 
        }//考虑是否反悔，不做之前做的任务 
    }

    printf("%lld", q.size());
    return 0;
} 

反悔自动机

基本思路

相比于反悔堆，反悔自动机更加高级一点，它能够自动的维护我们反悔的操作，通常适用于带限制的决策问题上。

下面我们来举一个很简单的例子，假如我们有四个数ABCD，AB当中只能选一个，CD当中只能选一个，问我们最后能收获的最大价值是多少。

假如刚开始我们选的是AC，那我们就可以把AC先删掉，把的值B变成B-A，D的值变成D-C，接下来的选择不考虑任何束缚。这样如果我们接下来再去选B，那这时我们选的值其实是B-A，加上之前选的A，相当于我们选了B没有选A，这就完成了返回操作——通过修改关联点的值让我们做到不选之前决定选的点而去选现在这个点。

这就是反悔自动机的大致思路。具体的反悔自动机又分为堆反悔自动机和双向链表反悔自动机两种，这样讲可能有点抽象，我们下面通过几个例题来看看反悔自动机的具体运用。

堆反悔自动机

题目描述

我们考虑这样一个问题：已知接下来N(N小于等于3e5)天的股票价格(第i天的股价为Pi),每天你可以买进一股股票,卖出一股股票,或者什么也不做.N天之后你拥有的股票应为0,问我们最大收益为多少。

算法讲解

我们先从简单的贪心开始考虑。首先我们可以贪心地对于每一天 i，如果我们可以卖出，那么贪心的选择之前的价格最小的一天 j，然后若 Pj < Pi 就可以在 j 天买入一股，然后在第 i 天卖出，这时候就仅需要一个priority_queue 就可以了。

但是还有一个问题，如何考虑下面这组数据呢？

1 2 5

可以发现，若贪心处理，则仅会在第 1 天买入一股，并在第 2 天卖出，赚到了 1 元。但是若将第 1 天的股票在第 3 天卖出，则可以获得高达 4 元的利润，比原答案不知道高到哪里去了。

所以我们尝试去考虑设计一种反悔策略，使所有的贪心情况都可以得到全局最优解。（即设计反悔自动机的反悔策略）

定义 Pbuy 为全局最优解中买入当天的价格， Psell 为全局最优解中卖出当天的价格，则：Psell−Pbuy=(Psell−Pi)+(Pi−Pbuy)，其中Pi 为任意一天的股票价格。即我们在Vi时把股票Vbuy的卖掉，再以Vi价格买进，再在Vsell时把买进的Vi股票卖掉，就相当于我们买价格最小(Vbuy)的股票去卖价格最大(Vsell)的股票，以期得到最大的利润。

具体到过程当中，我们先把当前的价格Pi放入小根堆一次(用于贪心买价格最小的股票去买价格最大的股票)，接着去判断当前的价格是否比堆顶大，若是比其大，我们就将差值累加计入答案相当于以Vi卖出，再将当前的价格放入小根堆（这次是反悔操作相当于再以Vi买入）。由于存在反悔操作和上面我们的那个式子，我们就能保证最后可以得到全局最优解。

而上面的等式一般被称为反悔自动机的反悔策略，因为我们并没有反复更新全局最优解，而是通过差值消去中间项的方法快速得到的全局最优解。

模板代码

这道题的模板题是CF上的一道题，题目是Buy Low Sell High，下面附上模板代码：

#include <cmath> 
#include <queue>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
struct node {
    int value;
    bool operator < (const node &v) const
    {
        if(value > v.value)return(true);
        else return(false);
    }//重载<号的定义，规定堆为关于价值的小根堆 
}a[330000];
priority_queue<node>q;//用优先队列代替手写堆 
int n;
long long ans = 0;//记录答案 

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i].value);
    //读入

    for(int i = 1; i <= n; i++) {
        q.push(a[i]);//用于贪心买价格最小的股票去买价格最大的股票
        if(!q.empty() && q.top().value < a[i].value) {//假如当前的股票价格不是最优解
            ans += a[i].value - q.top().value;;//将差值计入全局最优解 
            q.pop();//将已经统计的最小的股票价格丢出去
            q.push(a[i]);//反悔策略：将当前的股票价格再放入堆中，即记录中间变量（等式中间的Vi)
        }
    }

    printf("%lld", ans);
    return 0;
} 

双向链表反悔自动机

题目描述

我们考虑这样一个问题，假如我们要种树，我们在一条直线上挖了 n (n ≤ 5e5)个坑。这 n 个坑都可以种树，但为了保证每一棵树都有充足的养料，我们不会在相邻的两个坑中种树。而且由于树种不够，我们至多会种 m (m ≤ n / 2)棵树。假设我们能预知自己在某个坑种树的获利会是多少（可能为负），求我们的最大获利。

算法讲解

首先由于 m 是保证满足m ≤ n / 2的，所以我们的问题就一定有解，我们一定能找到 m 个坑使其不相邻，不用判断无解。接下来我们考虑如何解决这个问题。

在必定有解的情况下，我们可以很轻松的推出一个简单的贪心策略：每一步我们都在合法的情况下选择最大的价值。但显然这个策略是错误的，我们每次都选择了最大价值的点，这样的操作会导致相邻的两个点就不能选，而选择相邻两个点得到的价值可能更大。

为了解决这个问题，我们考虑涉及反悔自动机，其主要问题在于考虑如何设计反悔策略。我们同样用差值来达到反悔的目的。假设有 A，B，C，D 四个相邻的点。

A 点的价值为 a ，其他点同理。若：a + c > b + d则同理我们可以得到 a + c − b > d。

假如我们先选了 B 点，我们就不能选 A 和 C 两点，所以我们把AC两个点删掉。但只这么做显然是不对的，因为我们有可能不选B选AC会更优。所以我们可以新建一个节点 P , P 点的价值为 a + c − b ，再删去 B 点。这个过程就等价于我们把B点的价值变成 a + c − b，设这时的B点为B'点。我们让B'点连接AC点的邻居

就相当于改变之后的链表变成：

这样如果下一次选择的点是 B' 的话，就说明我们反悔了（即相当于 B 点没有选，选了 A 和 C ），可以保证最后的贪心最优解是全局最优解。

那我们如何快速完成上述操作和找出每一轮操作哪个点呢？我们可以使用双向链表完成上述操作，至于每次操作哪个点，我们可以使用大根堆维护现有点的权值最大值，使得最终在 O(nlogn) 的时间复杂度下快速求出全局最优解。

当然要注意权值有可能有负，而我们不一定要种 m 棵树，所以遇到贡献为负数时就break，输出答案就可以啦。

这里还有一点需要注意，我们上面只讨论了要删除的点在链表中间的情况，如果在链表两端的话，我们应该怎么办呢？其实更加简单，我们直接把它删掉，不设置反悔点就可以了。这是为什么呢？你看假如我们的端点是A，旁边是B，再旁边是C。如果我决定删除A，就代表A的值是大于B的值的，那我们就没有可能反悔了。这是因为假如我们反悔了选了B不选A，那我们得到的值b小于a，并且影响了C让C不能选了（选A时C是可以选的），可以说是赔了夫人又折兵，所以是不可能反悔的直接把A和B都删了就可以了。

模板代码

这道题的模板题也是很经典的，题目是种树，下面附上模板代码：

#include <cmath>
#include <queue>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
struct node {
    long long site, val;
    bool operator < (const node &v) const {
        if(v.val > val) return(true);
        else return(false);
    }////重载<号的定义，规定堆为关于价值的大根堆  
}now, x;
long long val[2200000];//价值 
long long vis[2200000], l[2200000], r[2200000];
//vis用于记录是否删除（1为删除），l，r为双向链表的左右邻居 
long long t, n, m;
long long ans;
priority_queue<node>q;
int main()  {
    scanf("%lld%lld", &n, &m);

    for(long long i = 1; i <= n; i++) scanf("%lld", &val[i]);
    while(!q.empty()) q.pop();

    for(long long i = 1; i <= n; i++) {
        now.site = i;
        now.val = val[i];
        vis[i] = 0;
        q.push(now);
    } 

    for(long long i = 2; i <= n; i++) l[i] = i - 1;
    for(long long i = 1; i <= n - 1; i++) r[i] = i + 1;

    l[1] = r[n] = 0;
    //预处理，制作堆和双向链表 

    for(long long i = 1; i <= m; i++) {
        x = q.top(); q.pop();
        while(vis[x.site] == 1) {
            x = q.top();
            q.pop();
        }//找到一个没有被删除的值最大的点 
        if(x.val < 0) break;
        ans +=  x.val;

        if(l[x.site] != 0) vis[l[x.site]] = 1;//删除左边的点 
        if(r[x.site] != 0) vis[r[x.site]] = 1;//删除右边的点 

        if(l[x.site] != 0 && r[x.site] != 0) {
            now.site = x.site;
            now.val = val[l[x.site]] + val[r[x.site]] - val[x.site];
            val[x.site] = val[l[x.site]] + val[r[x.site]] - val[x.site];
            r[l[l[x.site]]] = x.site;
            l[x.site] = l[l[x.site]];
            l[r[r[x.site]]] = x.site;
            r[x.site] = r[r[x.site]];
            q.push(now);
        }//如果不在链表两端 
        else if(l[x.site]) r[l[l[x.site]]] = 0;
        else l[r[r[x.site]]] = 0;   
        //如果在链表两端 
    }

    printf("%lld\n", ans);
    return 0;
}

拓展题目

其实还有很多类似的题目，比如种树的升级版[国家集训队]种树这题就只是把我们的链表变成了环形双向链表，只要把我们的l[1] = r[n] = 0改成l[1] = n; r[n] = 1;就可以了。并且这道题是严格种m棵，是要通过n < 2 * m来判断无解的。

此外就是最近北京航空航天大学校赛的一道题目，就是这套题（点击下载）的H题，这个问题由两部分组成，第一部分很显然是一前一后这么取就可以了，后一部分就是求差值后回归种树这题跑后悔自动机就可以啦，这道题有题解的不多，并且这道题我是写了一个有0号节点这个多余节点的一个环，其实和没有0号节点的链是等价的。这里附上代码：

#include <cmath>
#include <queue>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
struct node {
    long long num, val;
    bool operator < (const node &v) const {
        if(v.val < val) return(true);
        else return(false);
    }////重载<号的定义，规定堆为关于价值的大根堆  
}now, x;
long long a[2200000], b[2200000];
//a是原价值数组，b是做差后的价值数组 
long long vis[2200000], l[2200000], r[2200000];
//vis用于记录是否删除（1为删除），l，r为双向链表的左右邻居 
long long t, n, k;
long long ansa, ansb;
priority_queue<node>q;
int main()  {
    scanf("%lld", &t);
    for(long long o = 1; o <= t; o++) {
        scanf("%lld%lld", &n, &k);
        for(long long i = 1; i <= n; i++) scanf("%lld", &a[i]);
        sort(a + 1, a + n + 1);

        ansa = 0; ansb = 0;
        for(long long i = 1; i <= k; i++) ansa = ansa + (a[n - i + 1] - a[i]);

        while(!q.empty()) q.pop();

        for(long long i = 1; i < n; i++) {
            now.num = i;
            b[i] = a[i + 1] - a[i];
            now.val = a[i + 1] - a[i];
            vis[i] = 0;
            q.push(now);
        }

        for(long long i = 2; i < n; i++) l[i] = i - 1;
        for(long long i = 1; i < n - 1; i++) r[i] = i + 1;

        l[1] = r[n - 1] = 0;
        l[0] = n - 1;
        r[0] = 1;
        //预处理，制作堆和双向链表 

        for(long long i = 1; i <= k; i++) {
            x = q.top(); q.pop();
            while(vis[x.num] == 1) {
                x = q.top();
                q.pop();
            }//找到一个没有被删除的值最大的点 
            ansb +=  x.val;

            if(l[x.num] != 0) vis[l[x.num]] = 1;//删除左边的点 
            if(r[x.num] != 0) vis[r[x.num]] = 1;//删除右边的点 
            if(l[x.num] != 0 && r[x.num] != 0) {
                now.num = x.num;
                now.val = b[l[x.num]] + b[r[x.num]] - b[x.num];
                b[x.num] = b[l[x.num]] + b[r[x.num]] - b[x.num];
                r[l[l[x.num]]] = x.num;
                l[x.num] = l[l[x.num]];
                l[r[r[x.num]]] = x.num;
                r[x.num] = r[r[x.num]];
                q.push(now);
            }//如果不在链表两端 
            else if(l[x.num]) r[l[l[x.num]]] = 0, l[0] = l[l[x.num]];
            else l[r[r[x.num]]] = 0, r[0] = r[r[x.num]];
            //如果在链表两端 
        }

        printf("Case #%lld: %lld %lld\n", o, ansb, ansa);
    }
    return 0;
}

结语

通过这篇BLOG相信你对贪心这种算法已经有了新的认识。还记得上学期数据结构与算法课上讲到dijkstra的时候，我们的老师就问我们：“你觉得人贪不贪心啊？”我脱口而出不贪心，老师就告诉我们：“不对，人应该是贪心的。贪心是追求更好的一种态度，也是一种积极的态度。我们要学习它的态度但不要鼠目寸光。”最后希望你喜欢这篇BLOG！