算法简介
反悔贪心是对贪心策略的一种优化，有些时候贪心策略是错的，但如果可以撤销之前的操作，那么就会变为正确的。
反悔贪心主要有两种。一种是反悔堆，即将之前没有选择的操作加入一个（类）堆中，保证每次取出的堆顶都是当前没有选择的策略中最优的，若由于当前操作，则将其替换。还有一种是反悔自动机，可以设计一个自动机来决策当前的操作。
另外，有一种观点认为反悔贪心的本质是贪心模拟费用流，我认为是有一定道理的，这种观点也有利于解释反悔贪心的正确性。
经典例题
[USACO09OPEN] Work Scheduling G
反悔贪心板子题。
按任务按截止时间排序，若当前这个工作做得了（即已经做的件数小于这个工作的截止日期），那么直接做，并把它的价值放进优先队列中。若当前这个工作没时间做了，我们发现如果把前面一个工作去除，这个工作就做得了，于是对比小根堆顶的价值与他的价值，谁大就保留谁。
时间复杂度 $\Theta(n\log n)$。
[JSOI2007] 建筑抢修
反悔贪心板子题 $\times 2$。
我们发现每个建筑的贡献都是一样的。按建筑的 $T2$ 排序，一个个枚举，若当前建筑可以修（即之前已经选的建筑的 $T1$ 之和加上当前这个建筑的 $T1$ 不大于当前建筑的 $T2$），那么就直接将这个建筑的 $T1$ 加上并放进优先队列，并把答案 $+1.$ 若不能修，考虑到价值一样的情况下最小化总修理时间，那么将大根堆的堆顶取出，若其大于当前点的 $T1$，更新花费总时间。
时间复杂度 $\Theta(n\log n)$。
[P2107] 小 Z 的 AK 计划
反悔贪心板子题 $\times 3$。
首先按机房位置升序考虑，假设你有一种到了机房就必须 $\rm AK$ 的欲望（实际上是因为如果不 $\rm AK$ 这个机房，就没必要走到这里，而是在之前停下），那么如果当前的总用时加上 $\rm AK$ 这个机房的用时不到 $m$ 的时候，你就可以直接 $\rm AK$，并将这个机房的 $\rm AK$ 用时加入大根堆。若当前时间不够，就不断弹出堆顶，直到剩下的时间足够 $\rm AK.$ 一边枚举一边记录当前最优答案即可。
时间复杂度 $\Theta(n\log n)$。
[CF865D] Buy Low Sell High
首先考虑一个贪心，对每个数选择它后面第一个比他大并且还没被选择的数，容易发现这样是错的，$\rm Hack$ 数据如下 ：
于是我们考虑给上面那个贪心加上反悔操作，每次将当前值放入小根堆中，若当前枚举的这个数大于小根堆堆顶，那么就将其卖掉，获得 a[i] - Q.top() 的贡献。同时，为了之后能够反悔，我们还要将它也加入堆中，我们发现，如果后面还有一个数将其卖出，那么其等价于直接将此时的堆顶卖出。这样一来，如果我们认为某个点要卖出，那么它就要入堆两次。
时间复杂度 $\Theta(n\log n)$。
[国家集训队] 种树
考虑选了一个数以后会发生什么，它两边的数都不能选了。于是考虑在选了一个点之后，把它两边的数标为不能选，然后在原处加入一个权值为 $a_{i-1}+a_{i+1}-a_i$ 的点。每次取最大的点，若已标为不能选，就跳过，否则选他，然后将两边的点删去，更新链表顺序。
容易证明这样做是对的，并且可以用优先队列维护，时间复杂度 $\Theta(n\log n)$。