「反悔贪心」的再理解

· · 算法·理论

「反悔贪心」的再理解

0x00 引子

建议使用『进阶方法篇』反悔贪心系列 配合食用。

自从 CSP-S 被第一题搏杀之后，我的内心一直耿耿于怀，总想着怎么一雪前耻。在长达一周的做题和翻博客中，一个奇怪的概念逐渐在我心中长了出来，它就是 占位符。

这篇文章会系统性地盘一下占位符的概念，并尝试从原理上解释它是怎么构造出来的，以及什么时候该用它。

这也算弥补了一个遗憾吧。

0x10 无抽象占位的反悔贪心

先不管占位符那个抽象词，这章不提它，大家自己找找感觉，看看占位符到底是啥。

我们先从几道题入手，搞清楚反悔贪心大概是个什么工作原理。

提起反悔贪心，祖师爷级别的题目必须是：

P4053 [JSOI2007] 建筑抢修

这道题过于经典了，以至于很多小朋友都会做（我到现在才会）。

贪心的本质是什么，在我看来，是要用局部最优解去代换全局最优解，原因是全局最优解的时间复杂度太高了，我们只能退而求其次。然而有的时候局部最优解并不能代表全局最优解，那么贪心就废掉了。然而真的废了吗？实际上并没有。

贪心的本质是局部最优解，全局最优解的代表是 DP 和拓扑排序，两者的差距还挺大的。那我们可以估算一下，是否局部最优解和全局最优解之间差的不是特别大，就是可以通过一步 或者简单的修改，可以将局部最优解转换成全局最优解。

这道题就是一个典型。

我们考虑贪心去搞这个东西。怎么贪心呢？把所有的建筑最后的时间排一个序，然后从前往后找，到哪里就算到哪里了。

然而这个东西很容易被卡掉。

看这个数据：

2
100 100
5 101
5 101

你明明可以两个都搞的，但你在这里仅仅只能得到一个的价值。

那么我们考虑能不能使用一次更改让局部最优解变成全局最优解呢？

我们来考虑一下记录过去的操作，撤销过去的操作是否可行。经过我长时间的思考，发现确实可以。因为任何一个操作不会对于后面的操作造成影响，这里的造成影响指的是 时间的增加/贡献的增加会被造成影响。

于是我们使用一个大根堆来维护过去已经完成的操作，并且对于选的更烂的情况就直接 pop 和 ans-- 。

接下来我们要去找个加强版。

P2949 [USACO09OPEN] Work Scheduling G

不难发现，这里只是给加了个权值，然后把原来的时间长度去掉了。

那我们将计就计，直接按照权值排序，扔进小根堆里面等着 pop 就行了。

再加强一下。

P2107 小 Z 的 AK 计划

这道题简单来说就是说你有一个 m 的时间限制，然后每个东西可以选择拿或者不拿，拿了的话就是

\displaystyle \sum_{i=last}^{now}{x_i}+t_{now}

的代价。其中， last 是上一个拿的坐标， now 很明显吧......

这道题也很版，只是代价会随时变动。

我们将计就计，把 \displaystyle \sum_{i=last}^{now}{x_i} 从原来的式子里面掏出来，然后塞到 t 里。

这个 t 我们怎么处理呢？我们对于每一个新遇到的机房，直接先把它的路程加到前缀和里面，并且也把 AK 用的时间加到里面，并把 AK 的时间扔到大根堆里面，后面怎么做就不用我教了吧，聪明的孩子自己会动动手指敲个 pop 的。

哦对，最后不要忘记每次循环结束后记录答案，因为他在任意一个地方都可以结束。

我们来看一个小z的AK计划的加强。

P3545 [POI 2012] HUR-Warehouse Store

这道题就是把时间换成了商品，AK的时间换成了客人要的商品的数量，走的路程变成了进的货，要维护的把最大时间变成了不能后退。

实际上好像还不太一样……算了。

因为要维护哪一个客人的需求被满足了，所以我们要同时记录一个 i 在堆里面。后面怎么扔进去，怎么 pop 这个聪明的孩子会自己动的。

要不，中场休息一下\~做一下 [猫粮]，也许能成为有猫耳的猫娘哦\~

P11628 [WC2025] 猫粮

实际上这道题也是贪心，但不是反悔贪心。放在这纯粹是为了防止你们做题做魔怔了，看见贪心就想反悔。

坏了，昨天做的今天忘了咋整，不能我的大脑变成猫娘的形状了吧……

喵~ 米纳，让我们来看看这道喵粮题吧~

（此处省略一万字发癫过程，大意就是这题是构造 + 匹配，利用随机性质去填坑，而不是先选再撤回，喵粮全被我吃了，这题撤不回来的喵。）

大分讨还是太难了，狗修金快给我几袋优质喵粮补偿我~（逃）

咳咳，刚才被盗号了。继续讲反贪。

0x20 有抽象占位符的反悔贪心

我认为各位在做过或者看过前面的题解之后，可能对于占位符已经有了一点感觉了，下面会更详细的介绍占位符这个概念。

占位符简介

我根据询问 ChatGPT 、 Copilot 、 Gemini 、 Claude 四个AI的结果，使用 Gemini 总结出了一点心得，或许能够给各位和以后的自己带来一丝触动（？

占位符实际上是反悔贪心中构造的一种虚拟决策节点。

它不代表原始问题中的实体，而是 撤销上一轮贪心决策并转向替代方案 这个复杂行为的数值化身。它将“修改历史”的操作，转化成了“在当前进行一次新的选择”。

我们观察上面的四道反贪，不难发现：

题目 占位符 转移
建筑抢修 先前建筑用时 直接替换
work scheduling G 先前建筑权值 替换并更改答案
小Z的AK计划 AK用时 尝试去除后满足条件，之后替换并更改答案
P3545 需要的货物数量 尝试去除后满足条件，之后替换并更改答案

完全一样啊。

Gemini 总结说：

占位符是反悔操作的差价凭证，其权值是“新方案收益”和“旧方案收益”的差值。

它实际上是利用了代数抵消的原理工作，它利用了 X+(Y-X)=Y 的数学性质，让看似在累加的操作变成了替换。

Gemini 比喻说：

在优先队列中，占位符是一个时光机按钮。

  • 普通元素： 我现在要做这件事
  • 占位符元素：我现在要撤回我刚才干的，改做另一件事

而占位符的作用有三个：

  1. 延迟决策 允许未来修正错误，当前可以由着性子贪心。
  2. 线性化逻辑 将复杂的回溯或者状态转移，转化为堆上的推入/弹出操作
  3. 模拟最小费用流的反向边 在图论下，占位符就是网络流中的“退流”边，选择了话，就是让流流回源点，再流向另一条路径。

CF865D Buy Low Sell High

经典的股票买卖问题。占位符的标准体现。

我们每天拿到价格 p，先把 p 扔进小根堆（当作买入机会）。 如果 p> 堆顶，说明有钱赚！我们取出堆顶 x，假装赚了 p-x。

但这里有个问题：万一我不该在今天卖，而是应该留到后面更贵的日子卖呢？ 或者说，我是不是把今天当成了一个买入点更合适？

我们在 pop 掉 x 并计算利润的同时，要再往堆里扔一个 p。这就是占位符。

为什么要 push 两次？代码里通常是这样写的：

q.push(p);
if(p>q.top()){
    ans+=p-q.top();
    q.pop();
    q.push(p);
}

P1484 种树 及加强版 P1792

这道题也要用到上面的占位符思想。

我们考虑直接构造占位符，

对于当前种一棵树的操作，会使得两边的树不能种。那么我撤销这个操作种两边的树的话，他们的代价是固定的，是：

a_{left}+a_{right}-a_{now}

那么我们在 now 树上操作过后，因为它的两侧 left 和 right 树不能种了，我们就将这两棵树和当前树合在一起，并将这棵树的价值改成 a_{left}+a_{right}-a_{now} ，作为占位符使用。

但是用数组的话会消耗很大空间啊，咋整呢……双向链表！

请注意 P1792 这道题需要你搞一个循环，但 P1484 不需要。

接下来看一个加强版。

P3620 [APIO / CTSC2007] 数据备份

这道题不难看出来和上一个种树实际上很像，你把线化成点，选了一条线，两侧的线就不能选了，实际上和上一道题是一样的。

操作实际上没有什么不同，只是要看出来这个转化比较麻烦，如果看不出来的话就做不出来。

0x30 暴力判定法则

如果各位还没悟出来怎么判定能不能用反悔贪心，试试这个暴力方法（P3620 我就这么做的）：

  1. 试探：我如果撤销现在的操作换成另一个，差价是多少？
  2. 验证：这个差价是一个固定的数吗？还是会随着其他变化乱变？
  3. 结论：
    • 如果是固定的数（只和局部有关）\rightarrow 占位符能造出来 \rightarrow 可以用反悔贪心。
    • 如果算不清或者牵一发而动全身 \rightarrow 占位符造不出来 \rightarrow 放弃吧，直接去想 DP 或者网络流吧。

感谢各位观看本篇文章，如有疏忽还希望各位指正。

本篇文章在 Kotona 的回退博客 同时发布。

upd 26.1.14 : 改善语言风格，减少无用信息。原文在 反悔贪心 。