我们知道，贪心从来都是只顾现在，不太考虑将来的算法，然而，这种鼠目寸光的策略，在很多题目中并不成立，因为贪心算法只会紧紧抱住眼前的利益不放，而忽视了将来可能有更大的利益在等着它。
于是反悔贪心这一种特殊的贪心就出现了，它同样是贪心，但比普通的贪心更灵活，它学会了在合适的时机放下曾经拿起的东西，从而获得更大的利益。
当然，反悔贪心的本质还是贪心，所以反悔策略不是万能的，也会有考虑不全的情况，这时就得放弃贪心转而考虑其他算法。
P2107 小 Z 的 AK 计划
题意很简单，我们先看一下绝大多数题解是怎么讲这个题的：
- 考虑反悔贪心。我们尽可能 AK 所有路过的机房，如果 AK 当前机房后时间不够用，则从所有 AK 过的机房（包括当前）中取耗时最长的删掉，直到时间够用或者没有机房为止。 ——引用自 Sinktank的题解
非常简洁明了的把思路和代码的大体框架讲明白了，代码大致如下（先别写）：
常规写法
#include<bits/stdc++.h>
#define int long long
using namespace std;const int N=1e5+10;
struct Node{int x,t;
}a[N];
int n,m,ans;bool cmp(Node x, Node y){return x.x<y.x;
}
signed main(){cin.tie(0)->sync_with_stdio(0);cin>>n>>m;for(int i=1; i<=n; i++) cin>>a[i].x>>a[i].t;stable_sort(a+1, a+n+1, cmp);priority_queue<int> q;int lst=0;for(int i=1; i<=n; i++){int tim=a[i].x-lst+a[i].t;if(m<tim){while(!q.empty() && m<tim){// 为什么用while？int mx=q.top();if(mx<=a[i].t) break;m+=mx;q.pop();}}if(m>=tim){q.push(a[i].t);lst=a[i].x;m-=tim;}ans=max(ans, (int)q.size());}cout<<ans;return 0;
}
代码整体结构和前面的题区别不大，设当前考虑第 \(i\) 个机房，如果时间不够用，就反悔往外弹，直到时间够用了就把第 \(i\) 个加进堆里。
唯一的细节是，这个代码的反悔用了 while，而不是 if。
这就使人摸不着头脑了。用 while，意味着要一次性弹出多个元素，然而，如果弹出了多个元素，那么就算把第 \(i\) 个加回来，总数量还是净减少了。
虽然这样给后面的元素留下了更多机会，但从数量上看，似乎并不是最优解，为什么这样的贪心策略是正确的？
对于这一问题，大部分题解并没有给出明确解答，就算是更深入的题解，也没有解释清楚。所以在这里，会给出一个较为详细的解释。
先说结论，事实上，while 反悔也只反悔掉一个，做的事情和 if 没有区别。
这是为什么呢？想要证明贪心策略正确性，要么证明把反悔掉的加回来不会变优，要么证明在反悔之前的状态的答案，不会在继续往后扫描的过程中被更新。
这里使用后者进行说明。首先，进行反悔的条件是，当前时间不够用，并且堆顶的时间比 \(t_i\) 大，如果第二条不满足，那么把第 \(i\) 个加进去还不如不加，也不需要反悔。
因此，如果我们走到了 \(x_i\) 的位置要反悔，因为堆顶一定比 \(t_i\) 大，反悔一次时间肯定就够了。但代码中的 while 又是必需的，如果改成 if 会 wa，也就是说必须反悔多次，这似乎形成了矛盾。
但矛盾是不可能出现的，这只能说明，多出来的那些反悔次数，用在了别的环节，也就是上句话中我们最容易忽视的地方：走到 \(x_i\) 的位置。
是的，问题就这样迎刃而解了，我们忽略了剩下的时间可能甚至不够走到 \(x_i\) 的位置，如果真是这样，那么，\(x_i\) 往后的位置就都走不到了，这个答案也就不会继续扩展了，满足第二条证明方法。
这时要是还想走到 \(x_i\)，只能记录下当前答案，然后扔掉一些比较大的元素释放时间，直到足够走到为止。
现在能走到了，再考虑第 \(i\) 个要不要放进去，要不要反悔。
再仔细分析代码，我们发现，这个 while 循环实现的就是上面的过程，只不过把为了走到 \(x_i\) 释放时间的过程和对第 \(i\) 个元素做反悔的过程合在一起了，所以会很难理解，完全按上面的思路去写是这样的：
好理解的写法
#include<bits/stdc++.h>
#define int long long
using namespace std;const int N=1e5+10;
struct Node{int x,t;}a[N];
int n,m,ans;bool cmp(Node x, Node y){return x.x<y.x;}
signed main(){cin.tie(0)->sync_with_stdio(0);cin>>n>>m;for(int i=1; i<=n; i++) cin>>a[i].x>>a[i].t;priority_queue<int> q;stable_sort(a+1, a+n+1, cmp);for(int i=1; i<=n; i++){int tim=a[i].x-a[i-1].x;while(!q.empty() && m<tim){m+=q.top(), q.pop();}m-=tim;if(m<a[i].t && !q.empty() && q.top()>=a[i].t)m+=q.top(), q.pop();if(m>=a[i].t){q.push(a[i].t);m-=a[i].t;}ans=max(ans, (int)q.size());}cout<<ans;return 0;
}