后悔解法

思路是无论当前的选项是否最优都接受，然后进行比较，如果选择之后不是最优了，则反悔，舍弃掉这个选项；否则，正式接受。如此往复。

反悔贪心的分类：

反悔自动机：

即设计一种反悔策略，使得随便一种贪心策略都可以得到正解。** 基本的设计思路是：每次选择直观上最接近全局最优解的贪心策略，若发现最优解不对，就想办法自动支持反悔策略。（这就是自动机的意思） **具体题目具体分析。一般需要反悔自动机的题都是通过差值巧妙达到反悔的目的

反悔堆：

即通过堆（大根堆、小根堆）来维护当前贪心策略的最优解，若发现最优解不对，就退回上一步，更新最优解。** **由于堆的性质，使得堆的首数据一定是最优的，这就可以实现快速更新最优解。