专栏文章

「反悔贪心」的再理解

FFindFar
算法·理论参与者 8已保存评论 11

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
11 条
当前快照
1 份
快照标识符
@mke9riuu
此快照首次捕获于
2026/01/15 01:03
2 个月前
此快照最后确认于
2026/03/08 01:23
前天
查看原文

「反悔贪心」的再理解

0x00 引子

建议使用『进阶方法篇』反悔贪心系列 配合食用。
自从 CSP-S 被第一题搏杀之后，我的内心一直耿耿于怀，总想着怎么一雪前耻。在长达一周的做题和翻博客中，一个奇怪的概念逐渐在我心中长了出来，它就是 占位符。
这篇文章会系统性地盘一下占位符的概念，并尝试从原理上解释它是怎么构造出来的，以及什么时候该用它。
这也算弥补了一个遗憾吧。

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

先不管占位符那个抽象词，这章不提它，大家自己找找感觉，看看占位符到底是啥。
我们先从几道题入手，搞清楚反悔贪心大概是个什么工作原理。
提起反悔贪心，祖师爷级别的题目必须是：

[P4053 JSOI2007] 建筑抢修

这道题过于经典了，以至于很多小朋友都会做~~（我到现在才会）~~。
贪心的本质是什么，在我看来，是要用局部最优解去代换全局最优解，原因是全局最优解的时间复杂度太高了，我们只能退而求其次。然而有的时候局部最优解并不能代表全局最优解，那么贪心就废掉了。然而真的废了吗？实际上并没有。
贪心的本质是局部最优解，全局最优解的代表是 DP 和拓扑排序，两者的差距还挺大的。那我们可以估算一下，是否局部最优解和全局最优解之间差的不是特别大，就是可以通过一步 或者简单的修改，可以将局部最优解转换成全局最优解。
这道题就是一个典型。
我们考虑贪心去搞这个东西。怎么贪心呢？把所有的建筑最后的时间排一个序，然后从前往后找，到哪里就算到哪里了。
然而这个东西很容易被卡掉。
看这个数据：
CPP
2
100 100
5 101
5 101
你明明可以两个都搞的，但你在这里仅仅只能得到一个的价值。
那么我们考虑能不能使用一次更改让局部最优解变成全局最优解呢？
我们来考虑一下记录过去的操作，撤销过去的操作是否可行。经过我长时间的思考，发现确实可以。因为任何一个操作不会对于后面的操作造成影响，这里的造成影响指的是 时间的增加/贡献的增加会被造成影响。
于是我们使用一个大根堆来维护过去已经完成的操作，并且对于选的更烂的情况就直接 pop 和 ans-- 。
接下来我们要去找个加强版。

[P2949 USACO09OPEN] Work Scheduling G

不难发现，这里只是给加了个权值，然后把原来的时间长度去掉了。
那我们将计就计，直接按照权值排序，扔进小根堆里面等着 pop 就行了。
再加强一下。

P2107 小 Z 的 AK 计划

这道题简单来说就是说你有一个 mm 的时间限制，然后每个东西可以选择拿或者不拿，拿了的话就是
∑i=lastnowxi+tnow\displaystyle \sum_{i=last}^{now}{x_i}+t_{now}
的代价。其中， lastlast 是上一个拿的坐标， nownow 很明显吧......
这道题也很版，只是代价会随时变动。
我们将计就计，把 ∑i=lastnowxi\displaystyle \sum_{i=last}^{now}{x_i} 从原来的式子里面掏出来，然后塞到 tt 里。
这个 tt 我们怎么处理呢？我们对于每一个新遇到的机房，直接先把它的路程加到前缀和里面，并且也把 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)=YX+(Y-X)=Y 的数学性质，让看似在累加的操作变成了替换。
Gemini 比喻说：
在优先队列中，占位符是一个时光机按钮。
  • 普通元素： 我现在要做这件事
  • 占位符元素：我现在要撤回我刚才干的，改做另一件事
而占位符的作用有三个：
  1. 延迟决策 允许未来修正错误，当前可以由着性子贪心。
  2. 线性化逻辑 将复杂的回溯或者状态转移，转化为堆上的推入/弹出操作
  3. 模拟最小费用流的反向边 在图论下，占位符就是网络流中的“退流”边，选择了话，就是让流流回源点，再流向另一条路径。

CF865D Buy Low Sell High

经典的股票买卖问题。占位符的标准体现。
我们每天拿到价格 pp，先把 pp 扔进小根堆（当作买入机会）。 如果 p>p> 堆顶，说明有钱赚！我们取出堆顶 xx，假装赚了 p−xp-x。
但这里有个问题：万一我不该在今天卖，而是应该留到后面更贵的日子卖呢？ 或者说，我是不是把今天当成了一个买入点更合适？
我们在 pop 掉 xx 并计算利润的同时，要再往堆里扔一个 pp。这就是占位符。
为什么要 push 两次？代码里通常是这样写的：
CPP
q.push(p);
if(p>q.top()){
    ans+=p-q.top();
    q.pop();
    q.push(p);
}
  • 第一个 push：把今天当作一个新的买入点，以后可以卖出。
  • 第二个 push：如果我们以后用了这个占位符（即把它作为买入价配对了一个更贵的 pnxtp_{nxt}），收益计算过程如下：(p−min⁡)+(pnxt−p)=pnxt−min⁡(p-\min)+(p_{nxt}-p)=p_{nxt}-\min
    中间的 pp 奇妙地抵消了！这在物理上等价于：我们从未在第 ii 天卖出，而是直接把 min⁡\min 持有到了 nxtnxt 天才卖出。这个占位符 pp，就是那张“反悔并补差价”的票据。

P1484 种树 及加强版 P1792

这道题也要用到上面的占位符思想。
我们考虑直接构造占位符，
对于当前种一棵树的操作，会使得两边的树不能种。那么我撤销这个操作种两边的树的话，他们的代价是固定的，是：
aleft+aright−anowa_{left}+a_{right}-a_{now}
那么我们在 nownow 树上操作过后，因为它的两侧 leftleft 和 rightright 树不能种了，我们就将这两棵树和当前树合在一起，并将这棵树的价值改成 aleft+aright−anowa_{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 : 改善语言风格，减少无用信息。原文在 反悔贪心 。

评论

共 11 条评论，欢迎与作者交流。

正在加载评论...