反悔贪心

· · 算法·理论

如果一个贪心，直接做不好做（有操作/限制特别烦），只能求出一个局部的最优解，那么我们可以使用反悔贪心

反悔贪心字面意思上就是如果这一步的贪心不是最优解，那么就后悔了，退回到之前的某一次操作，进行另外一步贪心

具体地，反悔贪心有两种方法：

1.反悔堆：

每次把贪心操作记录到堆里，进行下一步贪心的时候，看一看和堆顶的操作相比是不是更优的，如果更优，直接把当前操作加入堆里；如果不优，直接反悔，把堆顶的那个操作拉出来。每一步贪心都把这一步操作放进堆里，这样就可以了

2.反悔自动机

一般需要反悔自动机的题都是通过差值巧妙达到反悔的目的

以例题为例：CF865D Buy Low Sell High

定义C_{buy}为全局最优解中买入当天的价格，C_{sell}为全局最优解中卖出当天的价格，则：

C_{sell}−C_{buy}=(C_{sell}−C_i)+(C_i−C_{buy}) 我们感性理解一下，如果你买卖股票一直赚钱，而且你可以在遇到更高价格股票的时候，撤销上一次的卖出操作，卖这个股票来获得更多钱，那么你一定会最终在全局最优解中买入和卖出 很明显，你不知道具体应该在什么时候买入或卖出，所以先买了再说，到时候再反悔。每当有新股票的时候，先加入堆里，看一看之前买过的股票里面，最小的那一个是不是比这个新股票价格小，如果小，那么答案就加上他们的差值，代表你买了之前那个股票然后在这时卖出（反悔了）。记得再把当前股票价格加到堆里（中间变量$C_i$）；如果大，那么就先把这个股票买了，到时候再卖掉 参考博客（写的很好） https://www.cnblogs.com/nth-element/p/11768155.html https://www.cnblogs.com/ycw123/p/16757567.html