反悔贪心：先选，再撤销最差的选择

1 做出的选择，能不能改？

在 贪心说明 中，我们通常寻找一种可以直接确定下来的选择：一旦选了，就不再回头。但有些问题里，新来的候选会让以前的选择显得不划算。

例如，你先答应了一个耗时很长的任务，后来又来了几个短任务。若以前的任务不能撤销，可能只能完成一个；若允许重新制定计划，就可能完成更多。

这里的“反悔”发生在计算方案时，不是执行到一半再倒流时间。我们维护的是一份可以修改的候选方案，最后才按题目的规则执行它。

本文先讲任务调度，再迁移到喝药水。需要会使用堆；不熟悉 priority_queue 时，可以先读 堆。

2 主模型：最多完成多少个任务

有 $n$ 个任务。任务 $i$ 耗时 $t_i>0$，必须在截止时间 $d_i\ge0$ 之前或恰好在该时刻完成。

• 从时刻 $0$ 开始，一次只能做一个任务；
• 所有任务一开始就已知，可以选择其中一部分并安排顺序；
• 一个任务必须完整完成，不能拆开；
• 每完成一个任务，收益都为 $1$，目标是完成的数量最多。

注意：任务只有“耗时和截止时间”，没有固定的开始时刻。这和 最大不相交区间数量：优先选择最早结束的 中已经确定了起止时刻的比赛，是两种不同的模型。

2.1 策略一：先做耗时最短的？

考虑两个任务：$A=(t=2,d=100)$，$B=(t=3,d=3)$。

先做较短的 $A$，再做 $B$，完成时刻是 $5$，$B$ 已经过期，只能完成一个。若先做 $B$ 再做 $A$，两者都能完成。

耗时少很重要，但不能忽略谁更早到期。

2.2 先解决顺序：按截止时间排序

如果一个可行方案中，相邻的两个任务 $x,y$ 满足 $d_x>d_y$，原顺序却是先 $x$ 后 $y$，可以交换它们。

设这两个任务开始前，已经花了 $T$ 时间。原方案可行，说明

换成先 $y$ 后 $x$ 后，$y$ 更早完成；$x$ 的完成时刻仍是 $T+t_x+t_y\le d_y<d_x$。后面的任务也不受影响。

不断消除这样的逆序，就得到截止时间非降序的方案。因此只需在按截止时间排序的序列里，决定每个任务选不选。 截止时间相同的任务，先后顺序任意。

2.3 策略二：按截止时间扫描，能放下就选，放不下就跳过？

只看三个任务：

按截止时间扫描，先选 $A$，总耗时变成 $6$。加入 $B$ 要花 $9>8$，跳过；加入 $C$ 要花 $10>9$，也跳过。最后只选了一个。

但撤销 $A$、改选 $B,C$，总耗时只有 $7$，能完成两个。

问题出在：“已经选了 A”被当成了不能修改的事实。 实际上题目只要求输出最终方案，完全允许在计算时把 A 换掉。

3 超时了，撤销谁？

设加入新任务之前，已选任务的总耗时是 $T$。把当前任务 $i$ 也加入后：

• 若 $T+t_i\le d_i$，暂时全部保留；
• 若 $T+t_i>d_i$，当前候选方案无法全部完成，必须舍弃一些任务。

所有任务对答案的贡献都是一个。若都只删一个，删掉耗时最长的任务，释放的时间最多，也就给后面的任务留下最多的时间。

这里必须把新任务也放进候选集合：最长的可能是旧任务，也可能恰好是新任务自己。

“释放的时间最多”解释了该考虑谁，但还没有证明算法正确。先把它实际运行一遍，再补上证明。

4 动手观察：新任务加入后，谁离开了？

在前面三个任务后，再加上 $D=(2,10)$、$E=(9,11)$：

演示中，“尝试加入”与“保留或撤销”分成两帧。出现超时的那一帧只是临时候选，不能当作合法方案。 注意 B 到来时撤销的是旧任务 A，而 E 到来时撤销的是 E 自己。

最后执行顺序是 B、C、D，完成时刻依次为 $3,7,9$，都没有超过各自的截止时间。

5 为什么只撤销一次就够？

加入任务 $i$ 之前，旧方案可行。旧任务的截止时间都不晚于 $d_i$，因此它们的总耗时满足 $T\le d_i$。

设这次弹出的最长耗时为 $L$。新任务也在堆中，所以 $L\ge t_i$。弹出后：

更早的约束也不会被破坏：若删的是旧任务，所有受影响的旧任务只会更早完成；若删的是新任务，就回到了旧方案。

因此每轮最多删除一个，if 就够。这里能写 if 是由这个不等式保证的，不是所有反悔贪心都只需撤销一次。

6 为什么撤销最长的，不会错过最优解？

仅仅说明“删掉后时间更少”，还不能排除一种疑问：最长任务的截止时间可能很早，换掉它，会不会影响后面某种更好的组合？

我们证明更直接的一件事：第一次出现超时的时候，删掉这个最长任务，至少还留得住一个最优方案。

6.1 第一个冲突前缀

暂时把没有被删除的任务都看作“仍可供最终答案选择”的候选，包括尚未扫描到的任务，并按截止时间排列。

设它的第一个超时前缀结束在任务 $i$。这意味着：

• 对每个更早的前缀 $h<i$，这个前缀里的全部候选任务都能按时完成；
• 到 $i$ 为止的候选任务全部做完，总耗时超过了 $d_i$。

记这个冲突前缀为 $P$，其中耗时最长的任务为 $m$。

6.2 把一个最优方案变成“不选 m”的最优方案

6.3 为什么这个证明对应一趟扫描？

算法扫描到超时任务时，堆里正好是当前第一个冲突前缀的全部候选。删除最长任务后，前面证明过：更早前缀仍然可行，当前前缀也恢复可行。

于是继续向后扫描，就是去寻找下一个冲突前缀。每一次删除都不降低尚存候选中的最优答案；扫描结束后，所有剩余任务已经能全部按时完成。因此剩余任务数就是原问题的最优答案。

7 对应真题：洛谷 P4053 建筑抢修

题目：luogu P4053: [JSOI2007] 建筑抢修。

只有一位工人，修复建筑 $i$ 需要 $T_1$ 秒，必须在 $T_2$ 秒之内完全修好。求最多能抢修多少座建筑。它与前面的任务模型直接对应：耗时是 $T_1$，截止时间是 $T_2$。

输入第一行是 $N$，随后 $N$ 行每行两个整数 $T_1,T_2$；输出最多能抢修的建筑数。数据范围为 $1\le N<150000$、$1\le T_1<T_2<2^{31}$。

1
2
3
4
5
6
7
8
9

输入：
4
100 200
200 1300
1000 1250
2000 3200

输出：
3

按截止时间排序后，依次为 $(100,200),(1000,1250),(200,1300),(2000,3200)$。最后尝试加入耗时 2000 的建筑，总耗时为 3300，超过 3200；删除这座建筑，留下三座。

7.1 完整 C++17 实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

#include <algorithm>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;

struct Task {
    long long duration, deadline;
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    if (!(cin >> n)) return 0;
    vector<Task> tasks(n);
    for (auto &task : tasks) cin >> task.duration >> task.deadline;
    sort(tasks.begin(), tasks.end(), [](const Task &a, const Task &b) {
        return a.deadline < b.deadline;
    });

    priority_queue<long long> chosen; // 大根堆：耗时最长的已选任务
    long long total = 0;
    for (const auto &task : tasks) {
        chosen.push(task.duration);
        total += task.duration;
        if (total > task.deadline) {
            total -= chosen.top();
            chosen.pop(); // 可能撤销旧任务，也可能撤销刚加入的任务
        }
    }
    cout << chosen.size() << '\n';
}

每个任务入堆一次，最多出堆一次，加上排序，总时间为 $O(n\log n)$，空间为 $O(n)$。

total 使用 long long：尝试加入的临时总耗时也要正确计算，不能只考虑最终可行方案的数值范围。

8 迁移：按顺序喝药水

题目：codeforces 1526C1: Potions (Easy Version)。

有一列药水，第 $i$ 瓶会使血量改变 $a_i$，可能加血，也可能扣血。初始血量为 $0$，必须从左向右考虑每一瓶，可以喝，也可以跳过，但任意时刻血量都不能小于零。求最多能喝多少瓶。

输入第一行是 $n$，第二行是 $n$ 个整数 $a_i$；输出最多能喝的瓶数。本题 $1\le n\le2000$，$-10^9\le a_i\le10^9$。

这里不能按药水数值排序。先遇到的负药水，不能使用后面才出现的正药水来“提前补血”。例如 $[-1,1]$ 按原顺序最多喝一瓶；若排成 $[1,-1]$，算出的两瓶不符合原题顺序。

8.1 同一个反悔动作，换一个撤销标准

从左到右扫描，先尝试喝下当前药水，并把它加入已选集合。

若血量变成负数，就撤销已选集合中数值最小的药水，也就是扣血最多的那一瓶。应该使用小根堆。

这也是原题样例，答案为 $5$。最终按原顺序喝第 $1,3,4,5,6$ 瓶，血量依次为 $4,5,2,3,0$，始终非负。

8.2 为什么只需撤销一次，并且不会破坏以前的血量？

设加入前的血量为 $H\ge0$，当前药水为 $a_i$，堆中最小值为 $x$。

若 $H+a_i<0$，则当前药水一定为负数，而 $x\le a_i<0$。撤销它之后：

若撤销的是以前喝过的一瓶负药水，从那一瓶开始的历史血量都会增加 $-x$，所以以前的非负约束不会被破坏；若撤销的是当前药水，则回到原状态。

8.3 为什么最大瓶数也能保证？把它转回任务模型

所有非负药水都可以喝：它们不会让任何位置的血量变差，而且每喝一瓶就增加一个计数。因此至少存在一个最优方案，喝下全部非负药水。

现在只需决定哪些负药水值得喝。对原序列中的每个位置 $i$，定义已经出现的非负药水提供的总血量：

一瓶负药水的“消耗”是 $c_i=-a_i>0$。在每个位置都不掉到负血量，等价于：

这就是前面的任务模型：消耗 $c_i$ 对应耗时，预算 $B_i$ 对应截止时间。而 $B_i$ 随扫描只增不减，原顺序已经是预算的非降序，完全不必给药水重新排序。

目标是选择尽可能多的负药水；加上固定会喝的全部非负药水，就是最多的总瓶数。预算不够时删除消耗最大的负药水，对应的正是删除最小的 $a_i$。前面“删除最长任务不降低最优答案”的证明，可以直接应用。

预算 $B_i$ 可能为零，这只表示前面还没有可用的血量，此时负药水必定不能保留。

8.4 完整 C++17 实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

#include <functional>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    if (!(cin >> n)) return 0;
    priority_queue<long long, vector<long long>, greater<long long>> chosen;
    long long health = 0;
    for (int i = 0; i < n; ++i) {
        long long effect;
        cin >> effect;
        chosen.push(effect);
        health += effect;
        if (health < 0) {
            health -= chosen.top(); // 堆顶为最小的负数，减去它就是恢复血量
            chosen.pop();
        }
    }
    cout << chosen.size() << '\n';
}

代码把所有已选药水都放进堆，写法更统一。触发反悔时堆顶一定为负数，所以不会误删正药水或零药水。

时间复杂度为 $O(n\log n)$，空间为 $O(n)$；血量累计使用 long long。

9 两道题放在一起看

它们的共同结构是：当前方案装不下所有候选时，删掉一个，保住尽可能多的选择，并把资源留给后面。

10 什么时候可以考虑反悔贪心？

看到下面的信号时，可以尝试这条思路：

1. 候选是逐个处理的，而处理顺序能让约束逐步检查，例如按截止时间或按原下标。
2. 先加入一个候选，可能让当前方案出现冲突。
3. 以前的选择仍可在计算方案时替换，题目没有要求立即且不可撤回地执行。
4. 可以比较“撤销谁”对后续资源的影响，并证明一次交换不会损失最优答案。

但这些只是找解法的线索，不是保证正确的判定条件。

11 自查：能否脱离“堆模板”解释清楚？

先独立完成 luogu P4053: [JSOI2007] 建筑抢修，再用同样的分析步骤完成 codeforces 1526C1: Potions。写代码前，试着回答：

• 为什么任务可以按截止时间排序，药水却不能按数值排序？
• “恢复当前可行”与“保证最终最优”，分别用了哪一段证明？
• 为什么每次先入堆再判断，堆顶有时是旧选择，有时是新选择？
• 为什么删掉的选择不必再放回来？
• 如果任务的收益不再相等，证明在哪一步失效？

能说清这些问题，才算掌握了反悔贪心，而不仅是记住了 priority_queue。

12 相关题解

暂无相关题解