一、一句话理解
普通贪心要求每一步都"看得准"，选完就不许后悔。而反悔贪心允许先斩后奏：每一步先按眼前的最优选进来，同时把"后悔药"准备好——一旦发现当前选择违反了限制（或有了更好的替代），就把之前选进集合里最差的那一个踢出去，腾出位置。踢谁、怎么补，由堆等数据结构高效完成。
生活类比：双十一抢了 10 张优惠券，结账时发现每单最多用 3 张。你不会重新挑选，而是直接扔掉面额最小的几张。如果之后又领到一张大额券，就把手里最小的那张换掉——这就是"反悔"。反悔贪心就是把这个动作交给小根堆自动完成。
零基础提示：本文反复出现的"小根堆 / 大根堆"就是 STL 的
priority_queue——堆顶永远是当前最值，插入、删顶都是 O(log n)。不熟悉先看预备知识 · 堆。二、经典模型：带截止时间的任务调度
贪心策略
- 把所有任务按截止时间从小到大排序。
- 依次考虑每个任务：无条件先把它的报酬放进一个小根堆（表示"先选了再说"）。
- 如果堆里的任务个数 超过了当前任务的截止时间 d，说明排不下了——把堆里报酬最小的那个任务弹出（反悔：放弃它）。
- 全部处理完后，堆里剩下的报酬之和就是答案。
堆的大小 ≤ 当前截止时间 d ⇒ 任意时刻方案都合法；弹出的永远是最不划算的
为什么是对的？
考虑前 i 个任务时，它们的截止时间都不超过 di，所以最多只能完成 di 个。堆里始终保持"报酬最高的至多 di 个"——这正是前 i 个任务能拿到的最大收益。归纳到最后一个任务，堆里就是全局最优。
三、图解：堆是如何"反悔"的
四、模板代码
struct Job { int d, p; }; // 截止时间、报酬
sort(a + 1, a + n + 1, [](Job x, Job y){ return x.d < y.d; });
priority_queue<int, vector<int>, greater<int>> q; // 小根堆存报酬
long long ans = 0;
for (int i = 1; i <= n; i++) {
q.push(a[i].p); ans += a[i].p; // 先选了再说
if ((int)q.size() > a[i].d) { // 排不下了
ans -= q.top(); q.pop(); // 反悔：踢掉最便宜的
}
}
printf("%lld\n", ans);五、进阶形态：P1484 种树（链表 + 堆的反悔）
问题：一条直线上 n 个坑位，第 i 个坑种树获利 a[i]（可能为负），要求任意两棵不相邻，至多种 k 棵，求最大获利。
反悔点在哪：用大根堆每次选当前收益最大的坑位 i。但选了 i 之后，i−1 和 i+1 就永远不能选了——如果这个决定将来被证明是错的呢？
反悔技巧：选 i 后，立刻往堆里塞入一个"后悔药节点"，权值为
a[i−1] + a[i+1] − a[i]。它的含义是：将来若选中它，就撤销 i，改选 i−1 和 i+1（净收益正好是三者之差）。同时在双向链表中把 i 删除，i−1 与 i+1 变成新邻居。- 双向链表维护"还活着的坑位"，大根堆存每个坑位的当前权值；两端加哨兵节点（权值 −∞）防越界。
- 取堆顶 i，若已被删则跳过；否则累加 a[i]，种下一棵。
- 令
a[i] = a[l] + a[r] − a[i]（l、r 为左右邻居），重新入堆；链表中将 l、r 删除并打标记。 - 重复至多 k 次：堆顶权值 ≤ 0 时停止（再选只会亏）——这正对应"至多 k 棵"。
再打个比方：这像下棋悔棋——你不是直接撤销，而是提前在棋盒里放一枚"悔棋子"，将来打出它就等价于"收回上一步、改下在旁边的两个点"。堆负责保证：每次拿到的都是当前最划算的决定或最划算的悔棋。
走查一遍：a = [3, 5, 2, 4]，至多 k = 2 棵
| 轮次 | 堆顶（坑位：权值） | 动作 | 累计收益 |
|---|---|---|---|
| 1 | ②：5 | 选②；①、③ 出局，插入"悔棋子"权值 3+2−5 = 0 | 5 |
| 2 | ④：4 | 选④（与②不相邻，合法） | 9 |
| 停止 | 悔棋子：0 | 堆顶 ≤ 0，再选不赚，停止（这就是"至多 k 棵"） | 9 |
六、易错点清单
- 排序关键字是截止时间，不是报酬；比较"堆大小 > d"时用当前任务的 d。
- 报酬累加用
long long（n ≤ 105，p ≤ 109 时会爆 int）。 - 种树题是直线排列（首尾不相邻），两端哨兵权值取 −∞；"至多 k 棵"意味着堆顶 ≤ 0 就停，不要傻跑满 k 次。
- 堆中"懒删除"：被合并掉的旧节点还在堆里，弹出时要判标记跳过。
识别信号：题目出现"最多选 k 个 / 有截止时间 / 相邻不能同时选 / 每个有收益求最大"——先想反悔贪心。
七、练习
- P2949 Work Scheduling（反悔堆模板题）
- P1484 种树（链表 + 堆反悔）
- 真题对照：CSP-S 2025 T1 社团招新（反悔思想）、2021 T1 廊桥分配