贪心算法详解：核心思想、策略设计、正确性证明与经典例题

贪心大概是所有算法思想里最像”常识”的一个。它的规则简单到一句话就能说完：每一步都挑当下看起来最好的那个，选完就往前走，不回头。

麻烦的地方也在这里。常识常常靠不住。同一个问题，换一种”看起来最好”的定义，结果可能就从最优变成了次优。更棘手的是，一个错的贪心策略往往在小数据上完全看不出问题——它会安静地给出一个看起来合理的答案，直到某个隐蔽的用例把它戳穿。

所以这篇文章不打算只讲”贪心怎么用”。它更想回答的是三个问题：什么样的局部选择是安全的、怎么证明它是安全的、以及怎么把它彻底推翻。

内容分十二个部分：先是概念和理论基础，然后是一套从题目推到算法的流程，接着用一整章展开正确性证明的五种思路，再按策略类型归纳实现模式，最后是四道完整例题、三组反例、复杂度推导、常见错误清单和学习路线。所有代码都是 C++17，可以独立编译运行，样例输入输出都给全了。

目录

• 第一章 贪心算法是什么
• 第二章 贪心算法的核心理论基础
• 第三章 如何设计一个贪心策略
• 第四章 贪心算法的正确性证明
• 第五章 贪心算法的经典策略与实现模式
• 第六章 经典例题详解
• 第七章 贪心算法的反例分析
• 第八章 贪心算法与其他算法的区别
• 第九章 时间复杂度与空间复杂度分析
• 第十章 贪心算法的常见错误与调试方法
• 第十一章 如何系统学习贪心算法
• 第十二章 总结

---

第一章 贪心算法是什么

从一个找零的例子说起

人民币有 1 元、5 元、10 元、20 元、50 元、100 元这些面额。现在要付 68 元，怎么付的纸币张数最少？

大多数人会这么做：

1. 看能用的最大面额，100 元超了，那就用 50 元。还剩 18 元。
2. 18 元用不了 20 元，用 10 元。还剩 8 元。
3. 8 元用不了 10 元，用 5 元。还剩 3 元。
4. 剩下的 3 元只能用 1 元，三张。

结果：50 + 10 + 5 + 1 + 1 + 1，6 张。

这套做法里没有任何回溯。每一步都是”在当前剩余的金额下，用能用的最大面额”，选完就不改了。这就是贪心算法：把求解过程拆成一系列决策，每一次决策都在当下来看是局部最优的，并且一旦做出就不再撤销。

什么叫”局部最优”

“局部最优”这四个字容易说得含糊，需要先定义清楚。

一个决策问题，通常可以写成这样的形式：有一个候选集合，我们要从中选出一个子集，使得某个目标函数最大或最小，同时满足一组约束。

贪心的每一步面对的是一个局部决策，它的输入只有两部分：还没处理完的候选，以及当前已经做出的选择所导致的状态。局部最优指的是，在这一步的输入下，按某个选择规则挑出的那个候选，是这一步能挑的最好的。

这个”选择规则”就是贪心的核心。它必须满足一个条件：只看这一步的输入，就能决定挑谁，而且不需要考虑未来会怎样。

在找零的例子中，选择规则是”面额最大的那张”。它的输入只有”还剩多少钱”，输出是”这次用哪张”。用不着预知后面会用到什么面额。

为什么局部最优不一定等于全局最优

这句话不能只当成警告来背，得看清它是怎么发生的。

还是看找零。假设某国发行了一套奇怪的面额：1 元、3 元、4 元。要凑 6 元。

贪心会这么走：能用的最大面额是 4（6 够用），拿 4，剩 2；2 用不了 3 和 4，只能拿 1，剩 1；再拿 1，剩 0。

结果 3 枚：4 + 1 + 1。

但实际上 3 + 3 只需要 2 枚。

问题出在哪？拿 4 的那一刻，它确实是当下能拿的最大面额，这个判断没有错。错的是这个判断没有考虑到它会把后面的选择空间压窄——拿走 4 之后剩下 2，而 2 只能拆成两个 1。如果当初拿 3，后面还剩 3，正好又是一张 3。

这就是贪心失败的根本原因：局部最优的规则只看得到当前这一步的收益，看不到这个选择对后续可行性的影响。当”这一步收益最大”和”为后续留下更好的空间”这两件事发生冲突时，贪心就有可能走偏。

反过来，前面的人民币例子之所以对，是因为这套面额之间存在倍数关系，使得”拿最大的”恰好也”留给后面的空间最优”。这个巧合不是普遍规律，只是这套面额的特性。

贪心算法如何构造一个解

把上面两段抽象一下。贪心算法通常按下面的骨架运行：

1. 把所有候选整理成一个有序的结构。常见做法是排序，或者建一个堆。
2. 按某种次序取出一个候选。
3. 判断它能不能和已选的部分相容。能，就选进来并更新状态；不能，就跳过。
4. 重复第 2、3 步，直到候选用完，或者已经凑够了解。

这张流程图里有一件事值得盯着看：没有任何一条线是往回改选择的。这是贪心和动态规划、回溯搜索之间最直接的分界线。动态规划会同时保留多个状态并互相比较，回溯会明确地撤销选择并换一条路重试，贪心两者都不做。

需要注意，第 3 步里的”相容”可以是不同性质的东西。在找零里，它是”不能用超了”；在区间调度里，它是”不能和已选区间重叠”；在最小生成树里，它是”不能形成环”。判断相容性的成本有时会主导整个算法的复杂度，这一点在第九章会详细算。

贪心适合解决什么类型的问题

从上面的分析能推出两个必要条件。

第一个是最优子结构。问题的最优解必须能由子问题的最优解拼出来。如果一个大问题的最优解和它任何一个子问题的最优解都没关系，那么”先解决子问题再拼”这条路就直接断了。

第二个是贪心选择性质。也就是”每一步都按同一个规则挑局部最优，最终能拼出全局最优”。这一条不是自动成立的，必须单独证明。

第二条比第一条苛刻得多。最优子结构是一个比较宽松的条件——动态规划也需要它。一个题目有最优子结构，只能说明”可以用某种方式从子问题推出全局最优”，完全不保证”每一步都挑局部最优”能得到那个最优。第二章会把这两种性质的差别讲清楚。

此外，贪心还隐含了一个工程上的要求：候选之间必须能排出先后。如果两个候选无法比较优劣，或者优劣关系依赖上下文，那么”挑最好的那个”就无从谈起。这也是为什么贪心的实现里排序和堆出现得如此频繁。

第二章 贪心算法的核心理论基础

这一章要建立一套能用来分析问题的语言。概念不多，但它们之间的关系比单个定义重要得多。

把问题写成数学形式

先统一记号。一个优化问题可以写成：

$$\begin{aligned} \text{最大化（或最小化）} \quad & f(S) \\ \text{使得} \quad & S \in \mathcal{F} \end{aligned}$$

其中 $S$ 是从候选集合 $E$ 中选出的子集，$\mathcal{F} \subseteq 2^E$ 是所有可行解组成的集合，$f$ 是目标函数。

• $S \in \mathcal{F}$ 时，称 $S$ 是一个可行解。
• 使 $f(S)$ 取到极值的那个可行解，称为最优解，记作 $S^$，它的目标值记作 $\mathrm{OPT} = f(S^)$。

用找零写一遍：候选集合 $E$ 是各种面额的纸币（每种视为若干个可区分的副本），$S$ 是选出的那一把纸币，约束 $\mathcal{F}$ 是”面值之和等于目标金额”，目标函数 $f(S) = -|S|$（取负是为了套用最大化的形式）。

用区间调度写一遍：$E$ 是所有区间，$\mathcal{F}$ 是”$S$ 中任意两个区间都不重叠”，$f(S) = |S|$。

有了这套记号，后面的话就能说得很精确了。

最优子结构

定义（最优子结构）：如果原问题的最优解，在去掉某一个决策之后，剩下的部分恰好对应某个子问题的最优解，则称该问题具有最优子结构。

用区间调度举例。选定了第一个区间 $a$ 之后，剩下的问题变成”在所有与 $a$ 不重叠的区间里选尽量多”，这是一个结构完全相同、规模更小的子问题。如果原问题的最优解里确实包含 $a$，那么去掉 $a$ 之后剩下的那部分，一定是这个子问题的最优解——否则可以用一个更好的子问题解替换掉它，得到一个比”最优解”更优的解，矛盾。

这个论证方式是通用的，可以写成一句话：最优解的任何一部分，都是对应子问题的最优解。

这里要强调一个容易混淆的地方。最优子结构保证的是”最优解可以分解”，它不保证“局部最优的选择一定出现在某个最优解里”。这两句话听起来接近，差别却决定了整套算法能不能成立。

举个反例来区分。0/1 背包问题显然有最优子结构——决定要不要装第 $i$ 件物品之后，剩下的就是容量变小的子问题，子问题最优解拼起来就是原问题最优解。但”优先装单位价值最高的物品”这个局部选择，不见得出现在任何最优解里（第七章有具体数值）。所以 0/1 背包有最优子结构，却不能用贪心解。

结论：最优子结构是贪心的必要条件，不是充分条件。

贪心选择性质

定义（贪心选择性质）：如果存在某个选择规则，使得按该规则做出的第一个局部选择，总能被包含在某个最优解里，则称问题具有贪心选择性质。

注意定义里的用词：是”某个最优解”，不是”所有最优解”。这一点很关键。一个问题可能有很多个最优解，贪心的选择只需要和其中一个对上就够了——后面的交换论证正是靠这个性质运作的。

同时也要注意，定义说的是”存在某个选择规则”，不是”任何选择规则”。同一个问题可能有一个规则满足贪心选择性质，另一些规则不满足。区间调度就是典型：按右端点排序的规则成立，按左端点或按区间长度的规则不成立（第七章有反例）。

这两个性质合起来，就构成了贪心算法正确性的骨架：

如果一个问题同时具有最优子结构和贪心选择性质，那么反复做贪心选择就能得到最优解。

简单说明一下为什么这两条够用。设第 $k$ 步的选择是 $g_k$。由贪心选择性质，存在一个最优解 $S^*_k$ 包含 $g_k$。把 $g_k$ 固定下来，剩下的部分就变成一个子问题；由最优子结构，这个子问题的最优解拼上 $g_k$ 就是原问题的最优解。于是对每一步都做同样的论证，归纳下去就得到完整的最优解。第四章会把这套论证展开成正式的证明。

可行解、最优解与局部决策的关系

这三个概念之间的层次关系可以这样理解：

候选集合 E
     │  按选择规则逐步筛选
     ▼
可行解集合 F  ──  目标函数 f 在其中取极值  ──▶  最优解 S*
     ▲
     │  每一步的局部决策都必须留在 F 内
局部决策 g_k

局部决策的作用是保证走出来的路一直在 $\mathcal{F}$ 里，不能越界。贪心算法的一个常见 bug 正是出在这里：选择规则本身没问题，但把候选选进来之后忘了检查可行性，于是产出了一个不可行的解。这类 bug 的表现往往不是”答案不够优”，而是”答案根本不合法”。

需要论证什么

最后把”要证明什么”写清楚。给定一个候选规则，要确认它能用，需要证明两件事：

(1) 可行性。按规则选出的 $S$ 一定满足 $S \in \mathcal{F}$。

(2) 最优性。$f(S) \geq \mathrm{OPT}$（对于最大化问题）。

第二条是真正的难点。第四章会给出五种不同的证明路线，它们各自适合的问题类型不同。这里先给出它们共同的骨架：

从任意一个最优解出发，证明它可以被改造成贪心解，而且每一步改造都不会让目标值变差。

这句话是交换论证的完整表述，也是绝大多数贪心证明的最终形态。归纳法、反证法、安全选择，本质上都是这句话的不同包装。

一个更抽象的角度：拟阵

最后提一个理论层面的结论，供有兴趣的读者继续深入。

有一类组合结构叫做拟阵（matroid），它由一个有限集合 $E$ 和一个满足特定公理的”独立子集族” $\mathcal{I}$ 构成。Rado 在 1957 年证明了：如果一个问题的最优解对应于某个拟阵的最大权独立集，那么”按权值从大到小逐个尝试、能加就加”这个贪心算法一定得到最优解。

这个定理的价值在于，它把”什么样的贪心一定对”从一个凭经验判断的问题，变成了一个可以验证公理的问题。最小生成树问题之所以能用 Kruskal 算法，正是因为图的所有无圈子集构成一个图拟阵。区间调度在特定形式下也能归入拟阵框架。

不过拟阵并不是贪心的全部。哈夫曼编码、带截止期的任务调度这些问题的最优性，都不能直接由拟阵定理推出，它们的证明仍然要靠交换论证一步步做。所以拟阵更适合当作一个”看到某类结构就能立刻判断”的快捷工具，而不能替代具体的证明。第十一章会给出继续学习这个方向的路标。

第三章 如何设计一个贪心策略

前面两章讲的是”贪心是什么”和”贪心成立的条件是什么”。这一章要解决的是更实际的问题：拿到一道题，怎么一步步走到一个能证明的策略上。

一套可操作的流程

把下面的九步当成一份检查清单就好。实际做题时顺序会来回跳，但每一步都不该被跳过，跳过哪一步，后面就可能在那里翻车。

第一步：明确优化目标。 先把它写成一句话，并且写清楚是最大化还是最小化。常见的目标有三类：最大化收益（求最多的区间、最大的利润）、最小化成本（最短的总距离、最少的操作次数）、最大化选择数量。

目标写错是最致命的错误，因为它会让后面所有推导都建立在错误的基点上。举个容易踩的坑：”让所有人等待时间最短”和”让最后一个完成的人尽早完成”是两个完全不同的目标，对应的最优解不一样，贪心规则也不一样。

第二步：分析约束条件。 约束决定哪些解是可行的。把它写清楚：$\mathcal{F}$ 到底规定了什么？是”总重量不超过容量”，还是”任意两个元素不相邻”，还是”任意前缀满足某个计数条件”？

约束和目标的组合方式往往决定了该用哪种算法。同样的目标配上不同的约束，可能需要完全不同的策略。第八章的两种背包就是最典型的例子。

第三步：找出影响结果的关键变量。 观察目标函数，看它跟哪些量有关。这个步骤的产物通常是一个表达式：

$$f(S) = \sum_{i \in S} g(x_i)$$

其中 $x_i$ 是候选 $i$ 的属性。如果目标函数能写成这种”每个元素独立贡献”的形式，那么排序贪心的可能性就很大。

第四步：提出候选的局部选择规则。 基于关键变量，提出一到两个具体的规则。常见的形态是”按某个属性升序/降序排，然后依次尝试”。

第五步：分析这个选择为什么可能是安全的。 用直觉找出支撑它的理由，比如”短作业先做能让后面的人少等”。这一步的产出是直觉，不是证明，但它决定了接下来往哪个方向找证明。

第六步：尝试构造反例。 这是最容易被跳过、也最不能跳过的一步。在投入时间去证明之前，先用几分钟试图推翻自己。构造反例的正确姿势是：从一开始，先在小规模上穷举，看看有没有和贪心结果不一致的输入。

第七步：寻找严格证明的路径。 如果反例没找到，就去证明它。第四章给的五种方法各有适用范围，通常先试交换论证，因为它最直接。

第八步：把数学思路翻译成算法。 证明里的”排序规则”就是代码里的比较函数，”选择”就是循环体。这一步有个对不上的常见后果——证明用的是 A 规则，代码写成了 B 规则，两者不一致，代码当然会错。

第九步：分析复杂度与边界。 时间花在哪（排序？堆操作？可行性判断？），空间能不能省，空输入、单元素、极端权重、相同权重这些边界怎么处理。第九章和第十章分别展开这两件事。

一个完整的推导示例

用一个具体的题目把这九步走一遍。

题目：有 $n$ 个人排队接水，第 $i$ 个人接满自己那桶水需要 $t_i$ 个单位时间。接水机只有一台，一次只能服务一个人。要求安排一个排队顺序，使得所有人的等待时间之和最小。

第一步，明确目标。 第 $i$ 个人的等待时间，是从开始排队到他接完水为止的这段时间。注意题目要最小化的是所有人的等待时间之和，而不是让最后一个人最早完成。

形式上，设排列为 $\pi = (\pi_1, \pi_2, \dots, \pi_n)$，第 $j$ 个人的等待时间是前面所有人的用时之和：

$$W(\pi) = \sum_{j=1}^{n} \sum_{i < j} t_{\pi_i}$$

目标是 $\min_{\pi} W(\pi)$。

第二步，约束。 约束只有一条：$\pi$ 必须是 $1..n$ 的一个排列，每个人恰好出现一次，不能重复也不能遗漏。这是一个纯排列问题，没有别的可行性约束。

第三步，关键变量。 把上面的双重求和交换次序：

$$W(\pi) = \sum_{i=1}^{n} t_{\pi_i} \cdot (n - i)$$

第 $i$ 个位置上的人，他的用时 $t_{\pi_i}$ 会被排在它后面的 $n-i$ 个人各等一次，所以被计入了 $n-i$ 次。

这个式子把结构说清楚了：每个 $t$ 都被乘以一个”权重”，权重只取决于它被放在第几个位置。位置越靠前，权重越大。

第四步，候选规则。 权重大的是位置靠前的位置（权重 $n-1$ 最大）。既然大的权重配小的数值能让总和最小，直觉就指向：把 $t_i$ 升序排列，小的放前面，大的放后面。

第五步，为什么可能安全。 用时短的人先做，他占用的时间少，后面所有人的等待都会缩短。反过来，如果让一个用时很长的人先做，那么所有人都要多等这么久。这个直觉和”权重大的位置配小数值”是完全一致的。

第六步，尝试反例。 拿 $n = 3$，$t = (3, 1, 2)$ 手算一遍。

贪心（升序）：1, 2, 3。等待时间分别是 0、1、3，总和 4。
另一种：3, 1, 2。等待时间 0、3、4，总和 7。
另一种：2, 1, 3。等待时间 0、2、3，总和 5。

三种排列里升序最小。再多试几组，找不到反例。

第七步，严格证明（邻项交换）。 证明的思路是：任何不是升序的排列，都能通过一次”擦掉一个逆序”的操作让它不变差。

设 $\pi$ 是一个排列，其中存在相邻的两个位置 $k$ 和 $k+1$，满足 $t{\pi_k} > t{\pi{k+1}}$。记 $a = t{\pik}$，$b = t{\pi_{k+1}}$，于是 $a > b$。

除这两个位置外，其他位置上的贡献不受影响。这两个位置上的贡献是：

$$a(n-k) + b(n-k-1)$$

交换它们之后，变成：

$$b(n-k) + a(n-k-1)$$

两者之差：

$$\big[a(n-k) + b(n-k-1)\big] - \big[b(n-k) + a(n-k-1)\big] = (a - b)\big[(n-k) - (n-k-1)\big] = a - b > 0$$

交换后总和严格变小了 $a - b$。也就是说，只要排列里还有一个相邻逆序对，交换它就能让目标函数严格更优。有限次这样的交换之后，逆序对全部消失，排列变成升序，而每一步都没有让结果变差——所以升序就是最优解。$\blacksquare$

这个证明之所以干净，是因为交换只影响了两个位置，其余部分的贡献完全抵消。这一点是选择”相邻交换”作为论证手段的关键原因：如果交换的两个元素不相邻，中间元素的贡献也会变化，式子就会变得难以处理。

第八步，翻译成代码。

// @Moxin1044 2026-10-15
// 排队接水：n 个人各需 t_i 单位时间，求所有人等待时间之和的最小值。
// 邻项交换论证得出排序规则 t_i 升序（正文第三章有完整推导）。
// 输入：n；随后 n 个 t_i
// 输出：最小等待时间之和
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int n;
    if (scanf("%d", &n) != 1) return 0;
    vector<long long> t(n);
    for (int i = 0; i < n; ++i) scanf("%lld", &t[i]);

    sort(t.begin(), t.end());

    long long total = 0, prefix = 0;       // prefix = 前面所有人的用时之和
    for (int i = 0; i < n; ++i) {
        total += prefix;                   // 第 i 个人的等待时间
        prefix += t[i];
    }
    printf("%lld\n", total);
    return 0;
}

示例输入：

4
3 1 2 4

示例输出：

10

验证一下：升序后是 1, 2, 3, 4，四个人的等待时间分别是 0、1、3、6，加起来 10。如果不排序按原顺序 3, 1, 2, 4：等待时间是 0、3、4、6，总和 13，确实更差。

第九步，复杂度与边界。 排序是唯一的非 $O(n)$ 操作，占 $O(n \log n)$；后面的扫描是 $O(n)$。所以总时间 $O(n \log n)$，额外空间 $O(1)$（$t$ 数组本身是输入，不计入额外空间）。边界上要注意 $n = 1$ 时输出 0；$t_i$ 可能很大，累加和要用 64 位整数，具体推导见第九章。

关键形式：邻项交换法

上面第七步用的方法值得单独命名：邻项交换法（也叫相邻交换法）。它是排序类贪心推导排序规则的标准工具，套路固定：

假设已经有两个相邻的元素 $a$ 在前、$b$ 在后，写出这种情况下目标函数与 $a, b$ 有关的部分。然后交换它们，写出交换后的部分。比较两者，得出”$a$ 在 $b$ 前面更优”成立的充要条件——这个条件就是排序的比较规则。

用数学写出来：设 $F(x \to y)$ 表示”$x$ 在前、$y$ 在后时，与该两者相关的目标函数值”。则

$$F(a \to b) \le F(b \to a) \iff \text{$a$ 应当排在 $b$ 前面}$$

如果这个条件最终化简成 $a$ 的某个量 $\le$ $b$ 的对应量，那么按这个量升序排序就是最优的。

这个方法有个前提：目标函数必须是”可加”的，交换两个相邻元素只会影响与它们相关的项。排队接水满足这个条件。当问题涉及两个属性的比较（比如”左边一个数、右边一个数”的双关键字题）时，化简出来的条件可能不是简单的单关键字升序，而需要交叉相乘来比较，甚至需要用不等式推导出形如 $a_1 b_2 \le a_2 b_1$ 的分组条件。

排水的证明只用了相邻交换。只要交换的是一对相邻元素，其余元素的位置不动，它们的贡献在相减时自动抵消——这是整个方法能成立的技术基础。

第四章 贪心算法的正确性证明

这一章是全文的核心。前面反复说”贪心必须证明”，这一章就来讲怎么证。

在展开具体方法之前，先把所有证明方法共同的目标写清楚。要证明的是一个形如这样的命题：

设贪心算法按规则 $R$ 依次做出选择 $g_1, g_2, \dots, g_k$，得到的解为 $G$。则对任意可行解 $S \in \mathcal{F}$，有 $f(G) \ge f(S)$。

几乎所有贪心证明的最后一步，都会落到下面这句话上：

从任意一个最优解出发，总可以把它改造成贪心解，而且改造过程中目标函数的值不变差。

这句话是交换论证的完整表述。数学归纳法、反证法、安全选择，说到底都是这句话的不同组织方式。理解这一点很重要，因为它说明贪心证明确实有一个统一的骨架，不需要为每种问题重新发明证明方法。

下面五种方法，区别不在于”要证什么”，而在于”从哪里切入”。

4.1 交换论证法

什么时候用：目标函数可加、约束是”集合层面的相容性”（不重叠、不成环、不超容量）的问题。这是最常用的方法，遇到贪心题先试它。

证明从哪里开始：从”任意一个最优解 $O$”开始。不要试图直接证明贪心解最优——那样会陷入对贪心过程的复杂分析。正确的切入点是站在最优解一边，看它和贪心解的第一个分歧点在哪里。

需要建立什么关键关系：证明在这个分歧点上，把最优解的选择换成贪心的选择，解仍然可行，而且目标值不变差。

如何完成：反复应用这个替换，每次至少消除一个分歧，因为解的元素个数有限，所以有限步之后最优解变成贪心解。

常见错误：只证明了”交换后目标值不变差”，忘了证明”交换后解仍然可行”。这两件事必须都做。只做前者，得到的结论是”存在一个更优的不可行解”，毫无意义。

下面用区间调度问题完整走一遍。

例题：区间调度

问题：给定 $n$ 个闭区间 $[l_i, r_i]$，选出尽可能多的区间，使得任意两个选出的区间都不重叠（端点相接算作不重叠）。

贪心规则：把所有区间按右端点升序排序，依次考察，只要当前区间的左端点不小于上一个已选区间的右端点，就选它。

定理：上述贪心算法得到的区间数等于最优解的大小。

证明。

设贪心依次选出的区间为 $g_1, g_2, \dots, g_k$。由于算法按右端点升序扫描，且只选出与之相容的区间，所以 $g_1, \dots, g_k$ 的右端点也是递增的：

$$r(g_1) \le r(g_2) \le \dots \le r(g_k)$$

设 $O$ 是任意一个最优解。把 $O$ 中的区间也按右端点升序排列，记作 $o_1, o_2, \dots, o_m$。

引理：对每个 $i = 1, 2, \dots, k$，都有 $r(g_i) \le r(o_i)$。（注意这个引理只在 $i \le \min(k, m)$ 时有意义。）

引理的证明（对 $i$ 做归纳）：

基础情况 $i = 1$：$g_1$ 是所有区间中右端点最小的那个（算法第一步取的就是它）。而 $o_1$ 是某个区间，所以 $r(g_1) \le r(o_1)$。

归纳步骤：假设 $r(g{i-1}) \le r(o{i-1})$，要证 $r(g_i) \le r(o_i)$。

由算法的定义，$gi$ 是在**所有满足 $l \ge r(g{i-1})$ 的区间中，右端点最小的那个**。

现在看 $oi$。由于 $O$ 是可行解，$o_i$ 与 $o{i-1}$ 不重叠，所以 $l(oi) \ge r(o{i-1})$。结合归纳假设 $r(g{i-1}) \le r(o{i-1})$，得到

$$l(o_i) \ge r(o_{i-1}) \ge r(g_{i-1})$$

这说明 $oi$ 满足 $l \ge r(g{i-1})$，它是算法在第 $i$ 步的合法候选之一。而 $g_i$ 是所有合法候选中右端点最小的，所以 $r(g_i) \le r(o_i)$。引理得证。$\square$

回到定理的证明：需要证明 $k \ge m$（贪心选的不少于最优解），再结合 $O$ 的最优性得到 $k = m$。

反设 $k < m$。那么贪心在第 $k+1$ 步停下来了，意味着不存在满足 $l \ge r(g_k)$ 的区间。

但由引理，$r(gk) \le r(o_k)$。而 $o{k+1}$ 是 $O$ 中的元素，$O$ 可行，所以 $l(o{k+1}) \ge r(o_k) \ge r(g_k)$。这说明 $o{k+1}$ 是一个满足 $l \ge r(g_k)$ 的区间，与”不存在这样的区间”矛盾。

所以 $k \ge m$。又因为 $O$ 是最优解，$k \le m$，故 $k = m$。$\blacksquare$

这个证明里，引理的作用是建立了一条”贪心的右端点始终不落后于最优解”的不等式链。这条链是整段论证的技术核心，它把”贪心的第 $i$ 个选择”和”最优解的第 $i$ 个选择”对应了起来。找这样的对应关系，是交换论证的主流套路。

4.2 数学归纳法

什么时候用：问题有明显的递归结构，或者贪心的每一步恰好把问题规模缩小 1，能写出”第 $n$ 步成立”和”第 $n+1$ 步成立”之间的关系。

证明从哪里开始：从最小规模（$n = 1$ 或 $n = 2$）开始，这里通常能直接验证。

需要建立什么关键关系：证明”规模 $n$ 的贪心选择”+”规模 $n-1$ 的贪心解”能拼成规模 $n$ 的最优解。

如何完成：归纳步骤往往又需要借助交换论证来证明”这一步的选择可以放进最优解”。

常见错误：只证明了”每一步都做了局部最优选择”，就宣称归纳完成。归纳需要的是”局部最优选择 + 子问题最优解 = 原问题最优解”，中间那个”+”号的正确性不能省。

下面用哈夫曼编码完整走一遍。

例题：哈夫曼编码

问题：给 $n$ 个字符，第 $i$ 个字符的频次是 $f_i$。要为每个字符设计一个二进制编码，使得任意一个编码都不是另一个编码的前缀（这叫前缀码，保证解码无歧义），并且加权总码长

$$\mathrm{WPL} = \sum_{i=1}^{n} f_i \cdot \ell_i$$

最小，其中 $\ell_i$ 是第 $i$ 个字符的编码长度。

前缀码与二叉树一一对应：每个字符对应一个叶子，从根到叶的路径上，走左孩子记 0、走右孩子记 1，这条路径就是该字符的编码。$\ell_i$ 就是叶子的深度。所以问题等价于：构造一棵有 $n$ 个叶子的二叉树，使 $\sum f_i \cdot \mathrm{depth}_i$ 最小。

贪心规则：每次从当前的候选集合中取出频次最小的两个节点，把它们合并成一个新节点（频次是两者之和），放回候选集合。重复 $n-1$ 次，直到只剩一个节点。

定理：哈夫曼算法构造出的树是带权路径长度最小的二叉树。

需要两个引理。

引理一（贪心选择性质）

陈述：设 $x, y$ 是所有字符中频次最小的两个，则必存在一棵最优树，使得 $x$ 和 $y$ 是最深的一对兄弟叶子。

证明（交换论证）：

取一棵最优树 $T$。设 $a, b$ 是 $T$ 中深度最大的一对兄弟叶子，记它们的深度为 $d$。不妨设

$$f_x \le f_y, \qquad f_a \le f_b$$

因为 $x, y$ 是频次最小的，所以 $f_x \le f_a$ 且 $f_y \le f_b$。又因为 $a, b$ 深度最大，所以 $\mathrm{depth}(x) \le d = \mathrm{depth}(a)$。

把 $T$ 中的 $x$ 和 $a$ 交换位置（连同它们的频次），得到新树 $T_1$。交换只改变了这两个位置上的字符，所以

$$\mathrm{WPL}(T) - \mathrm{WPL}(T_1) = f_x \cdot \mathrm{depth}(a) + f_a \cdot \mathrm{depth}(x) - f_x \cdot \mathrm{depth}(x) - f_a \cdot \mathrm{depth}(a)$$

整理：

$$= (f_a - f_x)\big(\mathrm{depth}(a) - \mathrm{depth}(x)\big) \ge 0$$

两个因子都非负：$f_a \ge f_x$ 是因为 $x$ 频次最小，$\mathrm{depth}(a) \ge \mathrm{depth}(x)$ 是因为 $a$ 在最深处。所以 $\mathrm{WPL}(T_1) \le \mathrm{WPL}(T)$，即 $T_1$ 也是最优树。

同理，在 $T_1$ 中把 $y$ 和 $b$ 交换，得到 $T_2$，仍有 $\mathrm{WPL}(T_2) \le \mathrm{WPL}(T)$。在 $T_2$ 中，$x$ 占了原来 $a$ 的位置，$y$ 占了原来 $b$ 的位置，两者都是深度 $d$ 的兄弟叶子。$\square$

注意交换式子里”两个因子都非负”这一步：如果把频次换成一个可能为负的量，这个论证立刻失效。贪心证明里出现乘积之积的形式时，一定要逐个因子检查符号。

引理二（最优子结构）

陈述：把频次最小的两个字符 $x, y$ 合并成一个新字符 $z$，令 $f_z = f_x + f_y$，得到一个规模变成 $n-1$ 的新问题。设 $T’$ 是这个问题的最优树。把 $T’$ 中 $z$ 所在的叶子替换成一个内部节点，其左孩子是 $x$、右孩子是 $y$，得到树 $T$。则 $T$ 是原问题的最优树。

证明：

先看 $T$ 与 $T’$ 的 WPL 关系。$T$ 比 $T’$ 多的部分，正是 $x$ 和 $y$ 这两个叶子各比 $z$ 深一层：

$$\mathrm{WPL}(T) = \mathrm{WPL}(T') + f_x + f_y \tag{1}$$

现在反设 $T$ 不是最优的。设 $U$ 是原问题的一棵最优树，且 $\mathrm{WPL}(U) < \mathrm{WPL}(T)$。

由引理一，可以假设 $U$ 中 $x, y$ 是最深的一对兄弟叶子（否则先做交换，把 $U$ 换成满足该性质的最优树）。把 $U$ 中的 $x, y$ 合并成一个频次为 $f_x + f_y$ 的叶子 $z$，得到新问题的一棵树 $U’$。同样有

$$\mathrm{WPL}(U') = \mathrm{WPL}(U) - f_x - f_y \tag{2}$$

由 $\mathrm{WPL}(U) < \mathrm{WPL}(T)$ 和 (1)(2) 得

$$\mathrm{WPL}(U') = \mathrm{WPL}(U) - f_x - f_y < \mathrm{WPL}(T) - f_x - f_y = \mathrm{WPL}(T')$$

这与 $T’$ 是新问题的最优树矛盾。因此 $T$ 是最优的。$\square$

定理的证明

有了两个引理，定理就是归纳法的一个直接应用。

对字符数 $n$ 做归纳。

基础情况 $n = 1$：只有一个字符，编码长度为 0（或者任意定长），显然最优。

归纳步骤：假设算法对所有不超过 $n-1$ 个字符的输入都能给出最优树。对 $n$ 个字符的输入，算法第一步合并频次最小的两个字符 $x, y$，得到一个 $n-1$ 个字符的新问题；由归纳假设，算法在新问题上给出的是最优树 $T’$；把 $T’$ 中的 $z$ 展开成 $x, y$ 两个叶子，得到 $T$。由引理二，$T$ 是原问题的最优树，而 $T$ 正是算法对 $n$ 个字符的输出。$\blacksquare$

这个证明的结构很典型：引理一处理”这一步的选择能不能进最优解”，引理二处理”选完之后剩下的子问题怎么接上”，定理用归纳法把两者串起来。 三个部分各司其职，缺一不可。

4.3 反证法

什么时候用：当”最优解的结构”比”最优解本身”更容易刻画时。典型场景是：能证明问题的最优值等于某个组合量的下界，比如”最优解至少需要这么多”。

证明从哪里开始：先给出最优解必须满足的下界。然后用反证法：假设有一个比贪心更优的解，推出它必须小于这个下界，矛盾。

需要建立什么关键关系：把贪心解的结构性质翻译成一个下界。

如何完成：证明”贪心解的大小 $\ge$ 某个量”且”任何可行解的大小 $\ge$ 同一个量”，两边夹住，得到相等。

常见错误：下界证错了方向。要证明的是”任何可行解都 $\ge$ 下界”，如果只证明”贪心解 $\ge$ 下界”，那说明不了任何问题。

下面用区间点覆盖（射气球）问题完整走一遍。

例题：用最少的点覆盖所有区间

问题：数轴上有 $n$ 个闭区间 $[l_i, r_i]$。要在数轴上放置尽量少的点，使得每个区间内部都至少含有一个点。点可以放在任意实数位置。

贪心规则：把所有区间按右端点升序排序。维护变量 last 表示上一个选中的点的位置，初始为负无穷。依次考察每个区间：

• 若 $l_i > \texttt{last}$，说明这个区间还没被覆盖，于是把点放在它的右端点 $r_i$ 上（放右端点是为了尽可能覆盖后面更多的区间），令 $\texttt{last} \gets r_i$，答案加一。
• 否则说明这个区间已经被上一个点覆盖了，跳过。

定理：贪心算法用的点数是最少的。

证明。

先看清贪心解的一个结构性质。

设贪心依次选中的点是 $p_1 < p_2 < \dots < p_k$。其中 $p_j$ 是在处理某个区间 $I_j$ 时被选中的。由算法的行为可以确定两件事：

1. $p_j = r(I_j)$，即点是该区间的右端点。
2. 选中 $pj$ 的条件是 $l(I_j) > p{j-1}$（当 $j \ge 2$ 时；$j = 1$ 时条件自动满足）。

把这两条合起来：对每个 $j \ge 2$，

$$r(I_{j-1}) = p_{j-1} < l(I_j)$$

即 $I_{j-1}$ 的右端点严格小于 $I_j$ 的左端点。这说明

$$I_1, I_2, \dots, I_k \text{ 是 } k \text{ 个两两不相交的区间}$$

（任意两个 $I{j_1}, I{j_2}$ 只要下标不同，由上面的不等式传递即得它们不相交。）

现在用反证法完成证明。

贪心解显然是可行的（每个区间都被某个点覆盖了），所以最优解的大小 $m \le k$。

反设存在一个更优的方案，只用 $m’ < k$ 个点就覆盖了所有区间。设这些点是 $q1, \dots, q{m’}$。

考察上面那 $k$ 个两两不相交的区间 $I_1, \dots, I_k$。任意一个点最多只能落在一个区间内部（因为它们两两不相交）。而每个区间内部都必须有点，所以覆盖这 $k$ 个区间至少需要 $k$ 个点：

$$m' \ge k$$

这与 $m’ < k$ 矛盾。所以 $m \ge k$。结合 $m \le k$，得到 $m = k$，贪心解就是最优解。$\blacksquare$

这个证明的关键在于把贪心的执行过程（每次选右端点、比较 last）翻译成了一个静态的结构性质（存在 $k$ 个两两不相交的区间）。反证法之所以能收尾，是因为有了这个结构性质，下界就变得显然了。

4.4 安全选择与最优解替换

前面三种方法是从不同角度切入同一种论证。把它们抽象出来，就得到了一个通用的分析框架。

定义（安全选择）：设 $S$ 是当前的部分解。如果存在一个最优解 $S^ \supseteq S$ 同时满足”$S^$ 也包含候选 $e$”，则称在当前状态下选择 $e$ 是安全的。

这个定义把贪心的每一步都变成了一个局部命题：这一步的选择是不是安全的？

如果每一步都安全，那么把所有贪心选择堆起来，就得到了一个解 $G$，且 $G$ 可以被扩展成某个最优解 $S^$。因为 $G$ 本身已经是完整的可行解（算法跑完了），所以 $G \subseteq S^$，再由 $|G| = |S^|$（都是完整解），得 $G = S^$，即贪心解最优。

这个框架的证明模板只有一句话：

找到候选 $e$ 和任意最优解 $S^$。若 $e \in S^$ 则已完成；否则把 $S^*$ 中某个元素换成 $e$，证明交换后仍然可行且目标值不变差。

注意”安全”和”最优”的区别。安全是局部性质：它只保证”存在某个最优解包含这个选择”。它并保证”这个选择一定出现在所有最优解里”。很多问题的多个最优解结构不同，贪心只会走到其中一个。所以证明里反复出现的措辞是”存在一个最优解”，而不是”每个最优解”——这个措辞不是文字游戏，它对应着证明的实际强度。

用同一个框架重看前面两个例子：

• 区间调度里的引理，说的正是”选择 $g_i$ 是安全的”。它证明了存在一个最优解，其第 $i$ 个区间的右端点不小于 $g_i$ 的右端点，从而可以用 $g_i$ 替换它。
• 哈夫曼的引理一，说的是”把频次最小的两个字符放在最深处”是安全的——存在一棵最优树具有这个性质。

两者的论证结构完全一样，只是”交换”的具体操作不同：一个是替换区间，一个是替换树上的叶子位置。识别出这一点，就能在遇到新问题时快速定位到该证明什么。

4.5 通过结构性质与递推关系

有一类问题，它的最优解满足某种”局部最优即全局最优”的结构定理。这时可以直接引用结构定理完成证明，不必逐项交换。

什么时候用：图论问题，尤其是那些能归入拟阵框架的问题（见第二章末）。

证明从哪里开始：先陈述结构定理（比如割性质），证明它；然后用归纳法维护”当前部分解属于某棵最优解”这个不变量。

需要建立什么关键关系：把贪心的每一步和结构定理的前提对上——贪心每步选的那条边，必须恰好是某个割上的最小边。

如何完成：归纳维护不变量，最后得到贪心解是一棵最小生成树。

常见错误：把结构定理当成理所当然。割性质本身是需要证明的，而且它的证明依赖”树中加边必成环”这个图论事实，不是纯逻辑操作。

下面用 Kruskal 最小生成树完整走一遍。

预备：割与割性质

设 $G = (V, E)$ 是一个连通无向图，每条边 $e$ 有权值 $w(e)$。

定义（割）：把顶点集 $V$ 分成两个非空部分 $(S, V \setminus S)$，称为图的一个割。一条边如果两个端点分别落在两侧，称它跨越这个割。

引理（割性质）：设 $(S, V \setminus S)$ 是图的一个割，$e$ 是所有跨越该割的边中权值最小的那条。则存在一棵最小生成树包含 $e$。

证明：

设 $T$ 是任意一棵最小生成树。若 $e \in T$，结论成立。

否则考虑 $T + e$：往一棵树里加一条不在树上的边，必然产生唯一的一个环，记这个环为 $C$。

边 $e$ 跨越割 $(S, V\setminus S)$，把环 $C$ 上除 $e$ 以外的边依次走一遍。这条路径从 $e$ 的一个端点出发（在 $S$ 侧）到另一个端点结束（在 $V\setminus S$ 侧），所以路径上至少有一条边也跨越这个割。记这条边为 $e’$。

由 $e$ 的最小性，$w(e) \le w(e’)$。

构造 $T’ = T + e - e’$：去掉环上的一条边，剩下的仍然是一棵生成树。它的权值是

$$w(T') = w(T) + w(e) - w(e') \le w(T)$$

而 $T$ 已经是最小生成树，所以 $w(T’) \ge w(T)$。两者夹住，$w(T’) = w(T)$，说明 $T’$ 也是最小生成树，且 $T’$ 包含 $e$。$\square$

Kruskal 算法的正确性

算法：把所有边按权值升序排序。维护一个森林（初始时没有边），依次考察每条边：若这条边的两个端点当前不在同一个连通块中，就把它加入森林；否则丢弃。加到 $|V| - 1$ 条边时结束。

定理：Kruskal 算法得到的 $|V| - 1$ 条边构成一棵最小生成树。

证明（维护一个不变量）：

不变量：在算法的任意时刻，当前已选出的边集 $A$ 都满足”存在一棵最小生成树 $T_A$ 使得 $A \subseteq T_A$”。

初始：$A = \varnothing$，取任意一棵最小生成树即可。

归纳步骤：设当前不变量成立，算法正在考察边 $e = (u, v)$。

情形一：$u, v$ 已经在同一连通块中。算法丢弃 $e$，$A$ 不变，不变量显然继续成立。

情形二：$u, v$ 在不同的连通块中。算法把 $e$ 加入 $A$。

设 $S$ 为 $u$ 所在的连通块（在森林 $A$ 中的连通块）。于是 $(S, V \setminus S)$ 是一个割，而 $e$ 跨越它（$u \in S$，$v \notin S$）。

要引用割性质，需要证明 $e$ 是所有跨越这个割的边中权值最小的。

反设存在一条跨越 $(S, V\setminus S)$ 的边 $e’’$ 满足 $w(e’’) < w(e)$。由于算法按权值升序处理边，$e’’$ 在 $e$ 之前就被考察过了。设 $e’’$ 的两个端点为 $u’’ \in S$、$v’’ \notin S$。

• 如果当时算法把 $e’’$ 加入了 $A$，那么 $u’’$ 与 $v’’$ 在 $A$ 中连通，于是 $v’’ \in S$（$S$ 是 $u’’$ 所在连通块的顶点集），矛盾。
• 如果当时算法丢弃了 $e’’$，说明 $u’’$ 与 $v’’$ 在那时已经连通。而边只会被加入、不会被删除，所以到考察 $e$ 的时刻它们仍然连通，于是仍然有 $v’’ \in S$，矛盾。

两种情形都矛盾，所以不存在这样的 $e’’$，$e$ 确实是跨越该割的最小权边。

由割性质，存在一棵最小生成树含 $e$。又由归纳假设，存在最小生成树 $T_A$ 含 $A$。现在需要一棵同时含 $A$ 和 $e$ 的最小生成树。这一步需要一点说明：如果 $e \in T_A$ 就完成了；否则，把割性质的证明过程用在 $T_A$ 上（$T_A$ 是含 $A$ 的最小生成树），得到的 $T’ = T_A + e - e’$ 仍是最小生成树，含 $e$，且因为 $e’ \notin A$（$e’$ 跨越割而 $A$ 中没有任何边跨越这个割——$A$ 的连通块以内不含跨割边），所以 $A \subseteq T’$。。

于是不变量得到维护。

终止：算法选出 $|V| - 1$ 条边，此时 $A$ 是一棵生成树，且由不变量存在最小生成树 $T_A \supseteq A$。两者边数相同（都是 $|V|-1$），所以 $A = T_A$，$A$ 就是最小生成树。$\blacksquare$

这个证明和交换论证的区别在于：它不逐项比较贪心解和最优解，而是维护一个”当前部分解总能被某棵最优解包含”的不变量。这种写法在处理图论、拟阵问题时比逐项交换更清晰。

4.6 证明里最常见的六个错误

把前面几种方法里容易出错的地方汇总一下。

错误一：用”显然”代替论证。 “这一步显然是最优的”不是证明。任何一处”显然”，都要能展开成具体的交换或计算。

错误二：只证可行性，不证最优性。 证明了算法输出的是合法解，不等于证明了它是最优解。这两件事必须分开做。

错误三：交换后不检查可行性。 交换论证里，交换后的解必须仍然是可行解。只算目标函数值的变化是不够的——那样只说明”存在一个更优的不可行解”。

错误四：把”存在最优解含这个选择”说成”所有最优解都含这个选择”。 前者是贪心需要的，后者通常不成立。搞混了会导致证明中出现无法弥补的漏洞。

错误五：归纳法漏掉基础情况或者归纳方向反了。 归纳法要求”小规模成立”+”由小推大”。写成”由大推小”是无效的。

错误六：把不等式两边的因子当成正数。 交换论证里经常出现 $(f_a - f_x)(\mathrm{depth}(a) - \mathrm{depth}(x)) \ge 0$ 这样的式子。这个不等式成立的前提是两个因子都非负，必须逐个确认。权重、容量、频次这些量如果可能为负或为零，论证就可能在符号上崩塌。

第五章 贪心算法的经典策略与实现模式

掌握了证明方法之后，还需要知道”贪心通常长什么样”。实际题目里，贪心的实现方式高度集中，绝大多数都能归入下面六种模式之一。

先提醒一句：下面的分类是按”实现形态”划分的，不是按”适用条件”划分的。 同一个模式可以对应很多正确性条件各不相同的题目，不能因为”某个题用了堆”就推断”另一个题也能用堆”。每一节末尾的”容易出错的地方”就是针对这种误推。

5.1 排序后贪心

基本思想：先用一个排序把所有候选整理成有序序列，然后按顺序扫描一遍，做一个不可撤销的选择。

适用场景：候选之间存在一个明确的优先级，而这个优先级不依赖选择过程——也就是说，排好序之后从头扫一遍就行，不需要动态调整顺序。

核心决策依据：排序的关键字。证明的责任就是用交换论证说明”为什么按这个关键字排序是对的”。

代表性问题：区间调度（按右端点）、排队接水（按用时）、分数背包（按单位价值）。

实现方式：

sort(items.begin(), items.end(), cmp);   // 关键：cmp 必须和证明里的规则一致
for (const auto& x : items) {
    if (可以选) { 选入; 更新状态; }
}

时间复杂度：$O(n \log n)$ 排序 + $O(n \alpha)$ 扫描（$\alpha$ 是单次可行性判断的成本）。如果扫描里嵌套了别的操作，要单独算。

容易出错的地方：

• 排序的关键字和证明里的规则不一致。证明用的是右端点，代码里写成了左端点——这类错误在小数据上往往也能通过，非常隐蔽。
• 忽略了相同关键字时的处理。当两个候选的关键字相等时，比较函数必须返回 false（两者互不小于），否则可能违反排序的严格弱序要求，导致未定义行为。C++ 标准库的 sort 在比较函数不满足严格弱序时会越界访问数组。
• 多个关键字混合时用减法而不是比较。写成 return a.x - b.x < 0; 这种形式，在 a.x - b.x 溢出时会得到错误结果。安全的写法是 return a.x < b.x;。

5.2 每次选择最大值或最小值

基本思想：不预先排序，而是每一轮从当前候选集合中挑出最大（或最小）的那个，处理完再更新候选集合。

适用场景：候选的处理顺序是确定的（每次都挑极值），但候选集合本身会随选择而改变。

核心决策依据：极值本身。这类问题的证明通常落在”选最大/最小的那个不会把最优解排除掉”上。

代表性问题：合并果子（哈夫曼编码的特例）、最小代价合并文件。

实现方式：最简单的写法是每次线性扫描找极值。

for (int step = 1; step < n; ++step) {
    // 线性找两个最小值
    int i1 = 0;
    for (int i = 1; i < m; ++i) if (a[i] < a[i1]) i1 = i;
    // ... 合并，更新数组
}

时间复杂度：$O(n^2)$。这个写法只在 $n$ 很小时可接受，$n$ 上万时就会超时——这时应该升级成 5.3 的堆实现。

容易出错的地方：

• 误以为线性扫描”常数更小所以更快”。当 $n$ 超过几千时，$O(n^2)$ 的劣势会迅速压倒常数优势。
• 合并后忘了把被合并的位置从候选集合里去掉，导致某一项被重复计入。

5.3 用优先队列维护候选集合

基本思想：把 5.2 里的”每轮线性找极值”换成”用堆维护，$O(\log n)$ 取极值”。

适用场景：反复需要取出极值，且候选集合在动态变化。

核心决策依据：堆顶元素。它和 5.2 的决策依据完全一样，只是取法变快了。

代表性问题：哈夫曼编码、带截止期的任务调度、合并果子、Dijkstra 的松弛。

实现方式（C++17）：

// 小顶堆：堆顶是最小值
priority_queue<long long, vector<long long>, greater<long long>> pq;
pq.push(x);          // 插入，O(log n)
long long v = pq.top();  // 查看堆顶，O(1)
pq.pop();                // 弹出堆顶，O(log n)
int sz = pq.size();      // 元素个数，O(1)

时间复杂度：$n$ 次插入加 $n$ 次弹出，共 $O(n \log n)$。

容易出错的地方：

• 堆的方向写反。 priority_queue<int> 默认是大顶堆（堆顶最大）。要取最小值必须写 greater<int>。这个错误不会导致编译失败，只会让结果静默出错。
• 对自定义结构体用堆时忘了重载比较运算符，或者把比较方向写反。
• pq.top() 在堆为空时是未定义行为。连续弹出时一定要先检查 size()。
• 以为堆支持删除任意元素。标准 priority_queue 只能访问和弹出堆顶。需要删除任意元素时，要么用 multiset，要么用”惰性删除”（弹出时检查该元素是否已失效）。

5.4 后悔贪心

基本思想：先临时接受当前候选，把它放进已选集合；如果这样导致约束被破坏，就从已选集合中撤销按某个准则最差的那个选择。也就是说，允许”反悔”，但每次只反悔一点。

适用场景：约束是累积性的（比如”最多处理 $t$ 个单位时间”），而候选的处理顺序有天然的先后（比如按截止时间排）。这时无法预先判断某个候选要不要留，只能边加边调整。

核心决策依据：从已选集合中撤销哪一个。通常是撤销”收益最小”的那个。

代表性问题：带截止期的任务调度、反悔型排序（比如”最多跳过 $k$ 个”这类题）。

实现方式：

sort(jobs.begin(), jobs.end(), 按截止时间升序);
priority_queue<long long, vector<long long>, greater<long long>> pq;  // 最小堆
for (const auto& j : jobs) {
    pq.push(j.profit);            // 先接受
    if ((int)pq.size() > j.deadline) pq.pop();   // 约束破坏，撤销收益最小的
}

时间复杂度：$O(n \log n)$。

容易出错的地方：

• 撤销的准则选错。 撤销”最早进来的”而不是”收益最小的”，正确性就没了。这个准则必须由证明给出，不能凭感觉选。
• 约束检查的时机搞错。是先加再判、还是先判再加，两种写法的结果不同，必须和证明里的表述一致。
• 以为”后悔贪心”是万能的。它只在特定结构下成立——撤销准则的正确性本身就需要证明。第六章的例题四会完整给出这套证明。

5.5 基于图结构的贪心

基本思想：在图上按某种顺序考察边或顶点，利用图的结构性质（连通性、割、环）做选择。

适用场景：问题的约束本身是图论性质的（”不成环”、”保持连通”、”最短路）。

核心决策依据：结构定理。比如 Kruskal 依赖割性质，Dijkstra 依赖”非负权下最近的未定顶点一定已确定最短距离”。

代表性问题：Kruskal / Prim 最小生成树、Dijkstra 单源最短路、拓扑排序。

实现方式：Kruskal 需要并查集判环；Prim 和 Dijkstra 需要优先队列。并查集的关键接口是：

struct DSU {
    vector<int> p, sz;
    explicit DSU(int n) : p(n + 1), sz(n + 1, 1) {
        for (int i = 1; i <= n; ++i) p[i] = i;
    }
    int find(int x) {                          // 路径压缩
        return p[x] == x ? x : p[x] = find(p[x]);
    }
    bool unite(int a, int b) {                 // 按大小合并，返回是否发生了合并
        a = find(a); b = find(b);
        if (a == b) return false;              // 已在同一集合
        if (sz[a] < sz[b]) swap(a, b);
        p[b] = a; sz[a] += sz[b];
        return true;
    }
};

这一段是可以直接拿去用的：把 struct DSU 放进文件、包含 <vector> 和 using namespace std; 就能编译。unite 的返回值表示”这次调用是否真的合并了两个不同的集合”——判环就是靠它的返回值（返回 false 说明两端已经连通，这条边会成环）。

时间复杂度：Kruskal 是 $O(m \log m)$ 或 $O(m \log n)$（取决于对边排序还是对顶点编号排序），其中 $m$ 是边数。并查集本身是 $O(m \alpha(n))$，$\alpha$ 是反阿克曼函数，在 $n$ 的一切实际取值下 $\alpha(n) \le 4$。

容易出错的地方：

• 把 Kruskal 的适用条件和 Prim 搞混。 两者都求最小生成树，但 Kruskal 只对边排序，处理的是”边集”；Prim 从一个点出发长树，处理的是”顶点集”。它们在非连通图上的表现不同（Kruskal 会自然输出最小生成森林，Prim 需要额外处理）。
• 并查集忘了路径压缩或按大小合并。只用其中一个，复杂度会退化成 $O(\log n)$ 甚至 $O(n)$ 每操作。
• 忘记判断图是否连通。Kruskal 选不满 $n-1$ 条边时，说明图不是连通的，此时没有生成树。

5.6 通过交换论证推导排序规则

基本思想：不猜测排序关键字，而是从目标函数出发，通过”相邻两项交换”的推导，算出排序规则应该是什么。

适用场景：候选有多个属性，排序关键字不是一眼能看出来的。

核心决策依据：把排序规则当成推导的结论而不是前提。

代表性问题：排队接水（按用时升序）、双关键字排队问题（按两属性之积排序）、国王游戏一类的邻项交换建模。

实现方式（推导模板）：

设置相邻两项 $a$ 在前、$b$ 在后，写出目标中与它们相关的部分 $F(a \to b)$；交换后是 $F(b \to a)$；令

$$F(a \to b) \le F(b \to a)$$

把 $a$ 的量移到一边、$b$ 的量移到另一边，得到形如 $g(a) \le g(b)$ 的判据，那么按 $g$ 升序排序就是最优的。

时间复杂度：由排序决定，通常是 $O(n \log n)$。

容易出错的地方：

• 推导出的判据含除法或浮点。 比如判据是 $\frac{a_1}{b_1} \le \frac{a_2}{b_2}$，直接写成浮点比较会因为精度问题出错。应当交叉相乘化为整数比较 a1 * b2 <= a2 * b1。
• 交叉相乘后整数溢出。两个 $10^9$ 的数相乘就超出了 32 位范围，必须用 64 位。
• 把”局部相邻最优”当成”全局最优”。邻项交换法只证明了”任何逆序对都可以被消除”，这依赖于持续交换能到达唯一的有序状态。如果比较关系不是全序（比如存在不可比较的两个元素），推导就要重新做。

六种模式对照

模式	决策依据	典型时间	代表问题	最容易踩的坑
排序后贪心	排序关键字	$O(n\log n)$	区间调度、分数背包	关键字与证明不一致
每轮取极值	极值	$O(n^2)$	合并果子（小规模）	规模变大后超时
优先队列	堆顶	$O(n\log n)$	哈夫曼、任务调度	堆方向写反
后悔贪心	撤销准则	$O(n\log n)$	带截止期调度	撤销准则选错
图结构	结构定理	$O(m\log n)$	Kruskal、Dijkstra	忘了判连通/判环
邻项交换推导	推导出的判据	$O(n\log n)$	排队接水、国王游戏	浮点比较、溢出

最后再强调一次：这张表的”决策依据”一列，每一项都需要独立证明。看到一道新题落在某个模式里，只说明”代码大概该这么写”，不说明”这个策略是对的”。

第六章 经典例题详解

这一章选四类问题做完整讲解。每道题都给完整的题目模型、算法思路、可直接编译运行的 C++17 代码、示例输入输出、复杂度分析和边界讨论。

前两道题的证明已经在第四章给出，这里侧重实现细节和工程上的坑；后两道题在第四章只给了框架，这里补齐完整证明。

例题一：区间调度

问题模型：给定 $n$ 个闭区间 $[l_i, r_i]$（$1 \le n \le 10^5$，$0 \le l_i \le r_i \le 10^9$），选出尽可能多的互不重叠的区间。区间 $[a,b]$ 与 $[c,d]$ 不重叠当且仅当 $b \le c$ 或 $d \le a$；端点相接（$b = c$）算作不重叠。

思路：按右端点升序排序，依次考察。维护 last 表示上一个选中区间的右端点，只要当前区间的左端点 $l_i \ge \texttt{last}$，就选中它并更新 last。

为什么按右端点排序：在第 $i$ 步，选择右端点最小的兼容区间，等价于”把剩余的时间窗口留得尽可能大”。第四章已经用归纳法证明了这条规则的最优性。这里补一句直觉：右端点越小，留给后面区间的空间越多，未来能塞进去的区间就越多。

代码：

// @Moxin1044 2026-10-15
// 区间调度：选出尽可能多的互不重叠区间。按右端点升序，能接就接。
// 输入：n；随后 n 行 l_i r_i（左闭右闭）
// 输出：最多可选区间数，以及具体选了哪些
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

struct Seg { int l, r; };

int main() {
    int n;
    if (scanf("%d", &n) != 1) return 0;
    vector<Seg> s(n);
    for (int i = 0; i < n; ++i) scanf("%d %d", &s[i].l, &s[i].r);

    sort(s.begin(), s.end(), [](const Seg& a, const Seg& b) { return a.r < b.r; });

    vector<Seg> chosen;
    int last = -1000000000;
    for (const Seg& x : s)
        if (x.l >= last) {                 // 与上一个已选区间兼容（端点相接也算兼容）
            chosen.push_back(x);
            last = x.r;
        }

    printf("%d\n", (int)chosen.size());
    for (const Seg& x : chosen) printf("(%d,%d) ", x.l, x.r);
    printf("\n");
    return 0;
}

示例输入：

11
1 4
3 5
0 6
5 7
3 9
5 9
6 10
8 11
8 12
2 14
12 16

示例输出：

4
(1,4) (5,7) (8,11) (12,16)

时间复杂度：排序 $O(n \log n)$，扫描 $O(n)$，总计 $O(n \log n)$。空间 $O(n)$（存储输入和结果），辅助变量只有 $O(1)$。

边界条件：

• $n = 0$ 时输出 0。代码里 scanf 会读到 0，循环不执行，输出空行，符合预期。
• 端点相接的区间视为兼容。如果题目要求”严格不重叠（$b < c$）”，把 x.l >= last 改成 x.l > last 即可。这个区别必须在读题时确认清楚，两种约定下的答案可能不同。
• 所有区间都重叠时输出 1；所有区间两两不重叠时输出 $n$。
• 坐标可能到 $10^9$，但只有 $10^5$ 个区间，不需要离散化。last 的初值应当取一个比所有坐标都小的数，代码里用 -1000000000。不要用 -1，因为坐标可能为 0。

例题二：哈夫曼编码

问题模型：给定 $n$（$1 \le n \le 10^5$）个字符及其频次 $f_i$（$1 \le f_i \le 10^9$），构造一棵带权路径长度最小的二叉树，并输出每个字符的编码。

思路：用一个小顶堆维护所有节点。每轮取出权值最小的两个节点，合并成一个权值为两者之和的新节点，把新节点放回堆。重复 $n-1$ 轮。

为什么用优先队列：每轮都要取”当前最小的两个”，而候选集合在变化。堆的取最小值是 $O(\log n)$，比线性扫描的 $O(n)$ 快得多。总共 $n-1$ 轮，堆实现的总代价是 $O(n \log n)$。

为什么合并最小两个是对的：第四章的引理一用交换论证证明了”存在一棵最优树让最小的两个字符处于最深位置且互为兄弟”，引理二证明了”把它们合并后，问题的最小子问题解可以展开成原问题最优解”，再用归纳法收尾。三步合起来就是算法正确性的完整依据。

代码：

// @Moxin1044 2026-10-15
// 哈夫曼编码：每次把权值最小的两个节点合并，用优先队列维护候选集合。
// 输入：n；随后 n 行 "字符 频次"
// 输出：带权路径长度 WPL，以及每个字符的编码
#include <cstdio>
#include <queue>
#include <vector>
#include <string>
using namespace std;

struct Node {
    long long w;          // 子树权值和
    int left, right;      // 左右孩子下标，叶子为 -1
    char ch;              // 叶子的字符，内部节点无意义
};

int main() {
    int n;
    if (scanf("%d", &n) != 1) return 0;

    vector<Node> tree;                                     // 节点池
    // 小顶堆：按权值从小到大弹出
    using P = pair<long long, int>;
    auto cmp = [](const P& a, const P& b) { return a.first > b.first; };
    priority_queue<P, vector<P>, decltype(cmp)> pq(cmp);

    for (int i = 0; i < n; ++i) {
        char buf[16]; long long f;
        scanf("%s %lld", buf, &f);
        tree.push_back({f, -1, -1, buf[0]});
        pq.push({f, (int)tree.size() - 1});
    }

    long long wpl = 0;                                     // 带权路径长度
    while (pq.size() > 1) {
        P a = pq.top(); pq.pop();
        P b = pq.top(); pq.pop();
        long long sum = a.first + b.first;
        wpl += sum;                                        // 每次合并的代价 = 新节点权值
        tree.push_back({sum, a.second, b.second, 0});
        pq.push({sum, (int)tree.size() - 1});
    }
    int root = pq.top().second;

    printf("WPL = %lld\n", wpl);
    // 从根做一遍 DFS，左路径记 0，右路径记 1
    vector<pair<string, char>> ans;
    vector<pair<int, string>> st;                          // 手写栈避免递归
    st.push_back({root, ""});
    while (!st.empty()) {
        pair<int, string> cur = st.back(); st.pop_back();
        int u = cur.first; string code = cur.second;
        if (tree[u].left == -1) { ans.push_back({code, tree[u].ch}); continue; }
        st.push_back({tree[u].right, code + "1"});
        st.push_back({tree[u].left,  code + "0"});
    }
    for (size_t i = 0; i < ans.size(); ++i)
        printf("%c : %s\n", ans[i].second, ans[i].first.c_str());
    return 0;
}

示例输入（这是一组经典的频次数据）：

6
a 45
b 13
c 12
d 16
e 9
f 5

示例输出：

WPL = 224
a : 0
c : 100
b : 101
f : 1100
e : 1101
d : 111

WPL 验算：$45 \times 1 + 12 \times 3 + 13 \times 3 + 16 \times 3 + 5 \times 4 + 9 \times 4 = 45 + 123 + 56 = 224$。堆中的合并代价累加也恰好是 $14 + 25 + 30 + 55 + 100 = 224$，两处一致。

顺带提一个恒等式：每次合并的代价之和，恰好等于最终的带权路径长度。原因是每合并一次，新节点的权值就会被”往上提一层”，而它在最终树中的深度正好等于它被合并后还参与合并的次数。这个恒等式提供了一个方便的自检手段：如果两种算法分别算出的 WPL 不一致，说明其中一处实现有问题。

时间复杂度：$n-1$ 轮合并，每轮 2 次弹出加 1 次插入，都是 $O(\log n)$，总计 $O(n \log n)$。最后的中序遍历是 $O(n)$。总时间 $O(n \log n)$。空间 $O(n)$（节点池和栈）。

边界条件：

• $n = 1$ 时只有根节点，WPL 为 0，编码是空串。很多编码题的评测数据里没有 $n=1$，但写代码时要注意 while (pq.size() > 1) 这个循环条件。如果写成 while (!pq.empty())，会在堆空时访问 top()。
• $f_i$ 最大 $10^9$，$n$ 最大 $10^5$，最深树的 WPL 可能达到 $10^9 \times 10^5 \times 10^5$ 量级，必须用 long long。合并时的中间结果 a.first + b.first 也要用 long long。
• 字符的编码长度不固定，存储编码必须用 string 而不是定长数组。
• 当频次存在相同时，不同的合并顺序可能产生形状不同但 WPL 相同的树。任何一个都是合法答案。如果评测要求输出特定的编码，通常题目会说明按字典序取最小的方案——这时需要给堆增加一个”下标小者优先”的次要比较，使相同权值时的处理顺序确定。

例题三：最小生成树（Kruskal）

问题模型：给定 $n$ 个顶点、$m$ 条边的连通无向带权图（$1 \le n \le 10^5$，$0 \le m \le 2 \times 10^5$，边权 $0 \le w \le 10^9$），求一棵最小生成树，输出总权值。

思路：把所有边按权值升序排序，依次考察。用并查集判断当前边的两个端点是否已经连通：不连通就选入（这样一定不会成环），连通就丢弃。选满 $n-1$ 条边时结束。

为什么按边权排序：第四章的割性质说明了，任何割上权值最小的边一定属于某棵最小生成树；而 Kruskal 每次选的边，恰好是”以当前某个连通块为一侧的割上的最小边”。正确性证明见 4.5 节，核心是维护”当前部分解总能被某棵最小生成树包含”这个不变量。

为什么需要判环：如果选入一条两端已经连通的边，就会在森林中形成一个环，而树不能有环。并查集恰好能 $O(\alpha(n))$ 判断这个条件。

代码：

// @Moxin1044 2026-10-15
// Kruskal 最小生成树 + 并查集判环
// 输入：n m；随后 m 行 u v w（顶点编号 1..n）
// 输出：最小生成树的总权值与所选的 n-1 条边
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

struct Edge { int u, v; long long w; };

// 并查集：路径压缩 + 按大小合并
struct DSU {
    vector<int> p, sz;
    explicit DSU(int n) : p(n + 1), sz(n + 1, 1) {
        for (int i = 1; i <= n; ++i) p[i] = i;
    }
    int find(int x) { return p[x] == x ? x : p[x] = find(p[x]); }
    bool unite(int a, int b) {
        a = find(a); b = find(b);
        if (a == b) return false;          // 已经在同一连通块，加这条边会成环
        if (sz[a] < sz[b]) swap(a, b);
        p[b] = a; sz[a] += sz[b];
        return true;
    }
};

int main() {
    int n, m;
    if (scanf("%d %d", &n, &m) != 2) return 0;
    vector<Edge> e(m);
    for (int i = 0; i < m; ++i) scanf("%d %d %lld", &e[i].u, &e[i].v, &e[i].w);

    // 贪心的第一步：把边按权值从小到大排
    sort(e.begin(), e.end(), [](const Edge& a, const Edge& b) { return a.w < b.w; });

    DSU dsu(n);
    long long total = 0;
    vector<Edge> chosen;
    for (const Edge& x : e) {
        if (dsu.unite(x.u, x.v)) {          // 不成环就选它（贪心选择）
            total += x.w;
            chosen.push_back(x);
            if ((int)chosen.size() == n - 1) break;   // 已经够了
        }
    }

    if ((int)chosen.size() != n - 1) { printf("图不连通\n"); return 0; }
    printf("MST 总权值 = %lld\n", total);
    for (const Edge& x : chosen)
        printf("%d - %d : %lld\n", x.u, x.v, x.w);
    return 0;
}

示例输入：

6 10
1 2 6
1 3 1
1 4 5
2 3 5
2 5 3
3 4 5
3 5 6
3 6 4
4 6 2
5 6 6

示例输出：

MST 总权值 = 15
1 - 3 : 1
4 - 6 : 2
2 - 5 : 3
3 - 6 : 4
2 - 3 : 5

验算：$1 + 2 + 3 + 4 + 5 = 15$。注意第 5 步考察的是边 1-4（权值 5），但此时 1 和 4 已经通过 1-3、3-6、6-4 连通，所以被丢掉了；随后 2-3（权值 5）的两端还在不同连通块，被选中，此时边数达到 $n-1 = 5$，算法结束。

时间复杂度：排序 $O(m \log m)$；并查集的 $m$ 次操作共 $O(m \alpha(n))$。总时间 $O(m \log m)$。空间 $O(n + m)$。

边界条件：

• 图不连通。Kruskal 选了不到 $n-1$ 条边就扫完了，此时不存在生成树。代码里显式判断并输出提示。如果题目保证连通，可以省略这个检查；但显式写出来更安全。
• $n = 1$ 时不需要任何边，应当输出 0。此时 n-1 == 0，循环第一次就会因为 chosen.size() == 0 == n-1 而提前 break 吗？不会——break 的判断在 if (dsu.unite(...)) 内部，不会被执行。所以循环会完整扫完 $m$ 条边。如果 $m$ 很大这会浪费时间，可以在循环前加一句 if (n == 1) { printf("0\n"); return 0; }。
• 边权可能为 0，比较函数没问题；但总权值要用 long long，$10^5$ 条边每条 $10^9$ 会超出 32 位范围。
• 重边和自环：自环（$u = v$）会因为 unite 返回 false 被自然丢弃；重边会选权值最小的那条，剩下的被丢弃。两种情况都不需要特殊处理。

例题四：带截止期的任务调度

问题模型：有 $n$ 项工作（$1 \le n \le 10^5$），第 $i$ 项工作需要 1 个单位时间完成，截止时间是 $D_i$（$1 \le D_i \le 10^9$），完成后获得收益 $P_i$（$1 \le P_i \le 10^9$）。机器在任意时刻只能做一项工作，工作必须在截止时间之前（含）完成。求能获得的最大总收益。

思路：把所有工作按截止时间升序排序，用一个最小堆维护当前已选工作的收益。处理每项工作时：

1. 先把它的收益压入堆（先接受）。
2. 如果堆的大小超过了该项工作的截止时间 $D_i$，就弹出堆中最小的收益（撤销最差的那个选择）。
3. 全部处理完后，堆中所有收益之和就是答案。

这是典型的后悔贪心：先接受，再在约束被破坏时撤销收益最小的部分。

为什么不能只看当前工作的收益：因为收益高的任务不一定该做。假如后面有一个收益更高但截止时间很紧的任务，为了它可能要放弃前面几个收益较低的任务——这个权衡在一开始看到低收益任务时是无法判断的，只能先放进来，等约束真的被破坏时再算总账。

为什么”先加再弹最小”能撤销掉正确的那个：这正是需要证明的地方。

可行性刻画

先把”哪些任务可以被安排”这件事说清楚。

引理一：设 $S$ 是一组工作。$S$ 能被安排在机器上（每项工作占一个时间单位，都在各自截止时间前完成）当且仅当对每个 $t \ge 1$，

$$\big|\{\,i \in S : D_i \le t\,\}\big| \le t \tag{3}$$

直观解释：(3) 说的是”截止时间在 $t$ 及之前的工作，数量不能超过 $t$ 个”。这些工作只能在时间 $1, 2, \dots, t$ 这 $t$ 个时间单位里完成，所以数量上界就是 $t$。这是必要条件。

证明：

必要性：若 $S$ 可安排，则所有 $D_i \le t$ 的工作都必须在时刻 $t$ 之前完成，占用的时间单位都在 ${1, \dots, t}$ 内，而这些时刻一共只有 $t$ 个，所以这类工作的数量不超过 $t$。(3) 成立。

充分性：设 (3) 对 $S$ 成立。把 $S$ 中的工作按截止时间升序排列：

$$D_{i_1} \le D_{i_2} \le \dots \le D_{i_p}$$

按这个顺序依次安排在时间 $1, 2, \dots, p$（第 $j$ 项工作安排在时刻 $j$）。需要验证第 $j$ 项工作在截止时间前完成，即 $j \le D_{i_j}$。

考虑第 $j$ 项工作，它的截止时间是 $D{i_j}$。由于排序是升序的，前 $j$ 项工作的截止时间都不超过 $D{i_j}$，即

$$|\{i \in S : D_i \le D_{i_j}\}| \ge j$$

对 $t = D_{i_j}$ 应用条件 (3)：

$$|\{i \in S : D_i \le D_{i_j}\}| \le D_{i_j}$$

两式合起来得 $j \le D_{i_j}$，正是需要的条件。所以按截止时间升序排列就是一个合法安排。$\square$

有了这个刻画，”$S$ 可行”就变成了一个纯计数的条件，处理起来方便多了。

算法行为的分析

把工作按截止时间升序排列，记第 $k$ 项工作的截止时间为 $d_k$，于是 $d_1 \le d_2 \le \dots \le d_n$。记算法处理完前 $k$ 项工作后的堆为 $H_k$。

引理二（堆的大小等于最大可行子集的大小）：对每个 $k$，$|H_k|$ 等于 ${1, \dots, k}$ 中可行的最大子集的大小。

证明（对 $k$ 归纳）：

记 $c_k$ 为 ${1,\dots,k}$ 中可行子集的最大大小。先证明一个通用的界：由引理一，取 $t = d_k$，任意可行子集 $A \subseteq {1,\dots,k}$ 都满足 $|A| = |A \cap {i : d_i \le d_k}| \le d_k$，所以

$$c_k \le d_k \tag{4}$$

基础情况：$k = 1$ 时，堆大小为 1（1 <= d_1 恒成立，因为 $d_1 \ge 1$），而 $c_1 = 1$。成立。

归纳步骤：假设 $|H{k-1}| = c{k-1}$，处理第 $k$ 项工作。

由于 $d{k-1} \le d_k$ 且 $|H{k-1}| = c{k-1} \le d{k-1} \le d_k$，压入之后堆的大小至多为 $d_k + 1$，所以最多只需要弹出一个元素。

• 情形 A：$|H{k-1}| < d_k$。此时不弹出，$|H_k| = |H{k-1}| + 1 = c{k-1} + 1$。
  一方面 $c_k \ge |H_k| = c{k-1} + 1$（$Hk$ 本身可行，见下面引理三的可行性部分）。
  另一方面，取 ${1,\dots,k}$ 中大小为 $c_k$ 的可行子集 $A$。若 $k \notin A$，则 $A \subseteq {1,\dots,k-1}$，得 $c_k \le c{k-1}$；若 $k \in A$，则 $A \setminus {k}$ 是 ${1,\dots,k-1}$ 的可行子集，得 $|A| - 1 \le c{k-1}$，即 $c_k \le c{k-1} + 1$。两种情形都有 $ck \le c{k-1}+1$。
  所以 $ck = c{k-1}+1 = |H_k|$。
• 情形 B：$|H_{k-1}| = d_k$。此时弹出一个，$|H_k| = d_k$。
  由 (4)，$c_k \le d_k$；又 $H_k \subseteq {1,\dots,k}$ 可行，所以 $c_k \ge |H_k| = d_k$。故 $c_k = d_k = |H_k|$。

两种情形都得 $|H_k| = c_k$。$\square$

引理三（前缀支配）：对每个 $k$ 和每个 $j \le |H_k|$，$H_k$ 中最大的 $j$ 个收益之和，不小于任意大小为 $j$ 的可行子集 $B \subseteq {1,\dots,k}$ 的收益之和。

证明（对 $k$ 归纳）：

记 $\mathrm{top}j(X)$ 为集合 $X$ 中最大的 $j$ 个收益之和（$j \le |X|$）。归纳假设 $\mathrm{PD}(k-1)$ 是：对每个 $j \le |H{k-1}|$ 和每个大小为 $j$ 的可行 $B \subseteq {1,\dots,k-1}$，$\mathrm{top}j(H{k-1}) \ge \mathrm{profit}(B)$。

先验证一个立刻要用的事实：若 $j - 1 \le |H|$，则 $\mathrm{top}j(H \cup {k}) \ge \mathrm{top}{j-1}(H) + p_k$。这是因为”$H$ 中最大的 $j-1$ 个”加上第 $k$ 项，构成了 $H \cup {k}$ 的一个大小为 $j$ 的子集，而 $\mathrm{top}_j$ 是所有大小为 $j$ 的子集里的最大值。

情形 A（不弹出）：$Hk = H{k-1} \cup {k}$。设 $B \subseteq {1,\dots,k}$ 是大小为 $j$ 的可行子集，$j \le |H_k|$。

• 若 $k \notin B$：$B \subseteq {1,\dots,k-1}$，由归纳假设 $\mathrm{profit}(B) \le \mathrm{top}j(H{k-1}) \le \mathrm{top}_j(H_k)$。
• 若 $k \in B$：$B \setminus {k}$ 是 ${1,\dots,k-1}$ 中大小为 $j-1$ 的可行子集。因为 $j \le |Hk| = |H{k-1}|+1$，所以 $j - 1 \le |H{k-1}|$，可以应用归纳假设：
  $\mathrm{profit}(B) = \mathrm{profit}(B \setminus {k}) + p_k \le \mathrm{top}{j-1}(H_{k-1}) + p_k \le \mathrm{top}_j(H_k)$。

情形 B（弹出）：此时 $|H{k-1}| = d_k$，$H_k = (H{k-1} \cup {k}) \setminus {m}$，其中 $m$ 是 $H_{k-1} \cup {k}$ 中收益最小的元素。

关键观察：$m$ 是 $H{k-1} \cup {k}$ 中的全局最小值，所以它在”最大的 $j$ 个”里永远排不上——只要 $j \le |H_k| = |H{k-1}| < |H_{k-1} \cup {k}|$。因此

$$\mathrm{top}_j(H_k) = \mathrm{top}_j\big(H_{k-1} \cup \{k\}\big) \quad \text{对一切 } j \le |H_k| \tag{5}$$

设 $B \subseteq {1,\dots,k}$ 是大小为 $j$ 的可行子集，$j \le |H_k|$。

• 若 $k \notin B$：$B \subseteq {1,\dots,k-1}$ 且大小为 $j \le |Hk| = |H{k-1}|$，由归纳假设 $\mathrm{profit}(B) \le \mathrm{top}j(H{k-1}) \le \mathrm{top}j(H{k-1} \cup {k}) = \mathrm{top}_j(H_k)$。
• 若 $k \in B$：$B \setminus {k}$ 是 ${1,\dots,k-1}$ 中大小为 $j-1$ 的可行子集，且 $j - 1 \le |H{k-1}|$，应用归纳假设并代入 $p_k$：
  $\mathrm{profit}(B) \le \mathrm{top}{j-1}(H{k-1}) + p_k \le \mathrm{top}_j(H{k-1} \cup {k}) = \mathrm{top}_j(H_k)$。

两种子情形都成立，$\mathrm{PD}(k)$ 得证。$\square$

定理：算法输出的总收益是最优的。

证明：设算法处理完全部 $n$ 项工作后堆为 $H_n$。

首先，$Hn$ 是可行解。逐个检查：由引理一的刻画，只需验证对每个 $t$，$|H_n \cap {i : d_i \le t}| \le t$。设 $t$ 给定，取 $k$ 为满足 $d_k \le t$ 的最大下标。处理完第 $k$ 项工作后，堆 $H_k$ 中所有元素的截止时间都 $\le d_k \le t$，所以 $H_k = H_k \cap {i : d_i \le t}$。而每次处理第 $k’$ 项工作时，若堆大小超过 $d{k’}$ 就会弹出，所以处理完第 $k$ 项后必有 $|H_k| \le d_k \le t$。又之后压入的工作截止时间都 $> t$（因为 $k$ 是满足 $d_k \le t$ 的最大下标），不会进入这个集合。所以 $|H_n \cap {i : d_i \le t}| = |H_k| \le t$。

其次，$H_n$ 是最优的。设 $S^$ 是任意可行解。由引理二，$|S^| \le |H_n|$，可以对 $S^$ 应用引理三（取 $k = n$，$j = |S^|$）：

$$\mathrm{profit}(S^*) \le \mathrm{top}_{|S^*|}(H_n) \le \mathrm{profit}(H_n)$$

（最后一步是因为 $|S^| \le |H_n|$，所以 $H_n$ 中最大的 $|S^|$ 个之和不超过 $H_n$ 的总和。）

所以算法输出的总收益不小于任意可行解，即是最优的。$\blacksquare$

代码：

// @Moxin1044 2026-10-15
// 带截止时间的任务调度（后悔贪心）：每项任务耗时 1 个单位，在截止时间前完成才有收益。
// 做法：按截止时间升序处理，用最小堆维护已选任务的收益；
//       一旦已选任务数超过当前截止时间，就丢掉收益最小的那个。
// 输入：n；随后 n 行 d_i p_i
// 输出：最大总收益
#include <cstdio>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;

struct Job { int d; long long p; };

int main() {
    int n;
    if (scanf("%d", &n) != 1) return 0;
    vector<Job> j(n);
    for (int i = 0; i < n; ++i) scanf("%d %lld", &j[i].d, &j[i].p);

    sort(j.begin(), j.end(), [](const Job& a, const Job& b) { return a.d < b.d; });

    priority_queue<long long, vector<long long>, greater<long long>> pq;   // 最小堆
    for (const Job& x : j) {
        pq.push(x.p);                      // 先接受
        if ((int)pq.size() > x.d) pq.pop(); // 时间不够了，撤销收益最小的那个
    }

    long long total = 0;
    while (!pq.empty()) { total += pq.top(); pq.pop(); }
    printf("%lld\n", total);
    return 0;
}

示例输入：

5
2 100
1 19
2 27
1 25
3 15

示例输出：

142

手算验证整个过程：

处理的工作（按截止时间排序后）	压入后堆内容	堆大小	截止时间	是否弹出
d=1, p=19	{19}	1	1	否
d=1, p=25	{19,25}	2 > 1	1	弹出 19
d=2, p=100	{25,100}	2	2	否
d=2, p=27	{25,27,100}	3 > 2	2	弹出 25
d=3, p=15	{15,27,100}	3	3	否

最终选中收益 15、27、100，总和 142。

作为对比，如果只按”收益优先”选，会得到 100、25、15 共 140，比 142 少。这正是”局部看起来最高收益”不如”整体可行下最优”的例子：25 的截止时间是 1，占掉了一个稀缺的时间单位；而 27 的截止时间是 2，可以和 100 一起在时刻 1、2 完成。收益上 27 比 25 高 2，正好是这个差值。

时间复杂度：排序 $O(n \log n)$；每项工作一次压入加至多一次弹出，$O(n \log n)$。总时间 $O(n \log n)$。空间 $O(n)$。

边界条件：

• $D_i$ 最大 $10^9$，但 $n \le 10^5$，所以最多只有 $n$ 项工作能被选中，堆的大小不会超过 $n$。不需要按 $D_i$ 开数组。
• $P_i$ 最大 $10^9$、$n$ 最大 $10^5$，总收益可能达到 $10^{14}$，必须用 long long。
• 截止时间可能重复。排序后相邻工作截止时间相同时，处理的先后不影响结果——引理二的证明只用到”处理完第 $k$ 项后堆大小不超过 $d_k$”这个性质，与同截止时间内部的顺序无关。
• 如果题目改成”工作耗时不一定为 1”，上述贪心不再适用，需要换成别的模型。引理一里”占用一个时间单位”这个假设是整个证明的基础。

第七章 贪心算法的反例分析

前面几章都在讲”怎么证明贪心是对的”。这一章讲反面：怎么确认一个贪心是错的。

这一章有一个前提必须先说清楚，否则后面的结论会被误用：

找到一个反例，足以证明一个策略是错误的。
找不到反例，不能证明一个策略是正确的。

这两句话不对称。反例是”存在性命题”的验证：只要给出一个具体的输入，贪心给出的答案严格劣于最优解，这个策略就被否定了，一劳永逸。而”没有反例”只是一个统计观察，它不能排除在小规模之外、或者在你没试到的输入上存在反例。

所以工作流程永远是两步：先用反例筛掉错的策略，再用证明确认剩下的那个是对的。只用第二步会浪费时间在注定失败的策略上；只用第一步则永远得不到可靠的结论。

案例一：硬币找零

策略：面额从大到小，能用就用。

输入：面额为 ${1, 3, 4}$，目标金额 6。

贪心的决策过程：

1. 当前剩余 6，能用的最大面额是 4（$6 \ge 4$），拿走 4，剩余 2。
2. 剩余 2，能用的最大面额是 1（$2 < 3$），拿走 1，剩余 1。
3. 拿走 1，剩余 0。

贪心结果：$4 + 1 + 1$，共 3 枚。

最优结果：$3 + 3$，共 2 枚。

失败原因：拿走 4 的那一刻，判断”4 是当前能用的最大面额”是正确的。问题在于这个判断只看了当前剩余金额，没有考虑”拿走 4 之后剩下的 2 只能被拆成两个 1”。如果当初拿 3，剩下 3，正好又是一枚 3。

换句话说：贪心的规则衡量的是”这一步的收益”，但最优性还取决于”这一步给后续留下了什么”。当这两个因素冲突时，贪心就可能出错。

用代码把这个反例复现出来（同时用完全背包的 DP 求出精确解作为对照）：

// @Moxin1044 2026-10-15
// 硬币找零：贪心策略在非规范面额系统上的反例
// 输入：第一行 n（面额个数）；第二行 n 个面额；第三行 M（目标金额）
// 输出：贪心的用币枚数与具体组合，以及 DP 求出的最少枚数
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int n;
    if (scanf("%d", &n) != 1) return 0;
    vector<int> coin(n);
    for (int i = 0; i < n; ++i) scanf("%d", &coin[i]);
    int target;
    if (scanf("%d", &target) != 1) return 0;

    // 贪心：面额从大到小，能用就用
    sort(coin.begin(), coin.end(), greater<int>());
    int rest = target;
    vector<int> pick;
    for (int c : coin)
        while (rest >= c) { rest -= c; pick.push_back(c); }

    // 精确解：f[x] = 凑出金额 x 所需的最少硬币数
    const int INF = 1000000000;
    vector<int> f(target + 1, INF);
    f[0] = 0;
    for (int x = 1; x <= target; ++x)
        for (int c : coin)
            if (x >= c && f[x - c] + 1 < f[x]) f[x] = f[x - c] + 1;

    printf("目标金额 %d\n", target);
    if (rest != 0) {
        printf("贪心：凑不出（差 %d）\n", rest);
    } else {
        printf("贪心：");
        for (size_t i = 0; i < pick.size(); ++i)
            printf("%d%s", pick[i], i + 1 == pick.size() ? "" : " + ");
        printf(" ，共 %d 枚\n", (int)pick.size());
    }
    if (f[target] >= INF) printf("最优：无解\n");
    else                  printf("最优：%d 枚\n", f[target]);
    return 0;
}

示例输入：

3
1 3 4
6

示例输出：

目标金额 6
贪心：4 + 1 + 1 ，共 3 枚
最优：2 枚

这个反例的适用范围：它否定的是”对任意面额系统都按最大面额贪心”这个一般性命题。它没有否定”对人民币面额系统按最大面额贪心”——后者是另一个命题，需要另外证明（人民币的面额设计使得贪心恰好最优，这是面额系统的性质，不是贪心算法的性质）。

把一个反例的作用范围说清楚，比反例本身更重要。“策略 P 在问题族 F 上不成立”和”策略 P 在这个具体输入上给出次优解”是两件事。

案例二：0/1 背包

策略：按单位价值 $v_i / w_i$ 从高到低排序，装得下就装。

输入：容量 $W = 50$，三件物品：

物品	重量 $w$	价值 $v$	单位价值 $v/w$
1	10	60	6.0
2	20	100	5.0
3	30	120	4.0

贪心的决策过程：

1. 物品 1 单位价值 6.0 最高，装下。剩余容量 $50 - 10 = 40$。
2. 物品 2 单位价值 5.0，装下。剩余容量 $40 - 20 = 20$。
3. 物品 3 需要 30 的重量，但只剩 20，装不下，跳过。

贪心结果：物品 1 + 物品 2，价值 $60 + 100 = 160$。

最优结果：物品 2 + 物品 3，价值 $100 + 120 = 220$。重量 $20 + 30 = 50$，刚好填满。

失败原因：单位价值排序在可分割的问题上是完全正确的（分数背包），因为可以按比例装。但 0/1 背包要求整件装或不装，于是”剩 20 装不下第 3 件”这件事变成了硬约束。贪心把最有价值的组合（物品 2 + 3）拆散了，原因就是它在第 3 步才发现容量不够，而这时已经无法反悔。

关键差别：与硬币问题不同，这里的失败不是因为”贪心看得太近”，而是因为问题的可行性约束是”离散”的。目标函数本身没问题，排序规则本身也没问题；出问题的是”按这个顺序取”和”取整”这两件事不能同时满足。

这一点在第八章会展开。

案例三：区间选择的不同排序规则

问题：第三章例题一那个问题，换成不同的排序规则。

输入：

4
0 10
1 4
4 8
3 5

也就是四个区间：$[0,10]$、$[1,4]$、$[4,8]$、$[3,5]$。

规则一：按右端点升序（正确的规则）

排序后：$[1,4]$、$[3,5]$、$[4,8]$、$[0,10]$（右端点依次是 4、5、8、10）。

1. $[1,4]$：第一个，选中，last = 4。
2. $[3,5]$：$3 < 4$，与已选区间重叠，跳过。
3. $[4,8]$：$4 \ge 4$，端点相接，兼容，选中，last = 8。
4. $[0,10]$：$0 < 8$，跳过。

结果：2 个（$[1,4]$ 和 $[4,8]$）。

规则二：按左端点升序

排序后：$[0,10]$、$[1,4]$、$[3,5]$、$[4,8]$。

1. $[0,10]$：第一个，选中，last = 10。
2. 其余三个区间的左端点分别是 1、3、4，全都小于 10，全部跳过。

结果：1 个。比最优少。

失败的机理很直白：$[0,10]$ 的左端点最小，但它几乎横跨了整个数轴，选它等于把后面所有的机会都堵死了。”左端点小”和”占用空间少”完全是两件事。

规则三：按区间长度升序

排序后：$[3,5]$（长度 2）、$[1,4]$（长度 3）、$[4,8]$（长度 4）、$[0,10]$（长度 10）。

1. $[3,5]$：最短，选中，last = 5。
2. $[1,4]$：$1 < 5$，跳过。
3. $[4,8]$：$4 < 5$，跳过。
4. $[0,10]$：$0 < 5$，跳过。

结果：1 个。同样比最优少。

失败的机理：最短的区间 $[3,5]$ 正好横跨在 $[1,4]$ 和 $[4,8]$ 之间，选它就把这两个本来可以同时选中的区间都排除掉了。”长度最短”和”最不占空间”也不是一回事。

用代码把三种规则并排跑一遍：

// @Moxin1044 2026-10-15
// 同一组区间，三种排序规则的对比：右端点升序 / 左端点升序 / 区间长度升序
// 输入：n；随后 n 行 l_i r_i
// 输出：三种规则各自能选出多少个互不重叠区间
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

struct Seg { int l, r; };

int run(vector<Seg> s, int mode) {
    if (mode == 0)      sort(s.begin(), s.end(), [](const Seg& a, const Seg& b) { return a.r < b.r; });
    else if (mode == 1) sort(s.begin(), s.end(), [](const Seg& a, const Seg& b) { return a.l < b.l; });
    else                sort(s.begin(), s.end(), [](const Seg& a, const Seg& b) { return a.r - a.l < b.r - b.l; });
    int cnt = 0, last = -1000000000;
    for (const Seg& x : s)
        if (x.l >= last) { ++cnt; last = x.r; }
    return cnt;
}

int main() {
    int n;
    if (scanf("%d", &n) != 1) return 0;
    vector<Seg> s(n);
    for (int i = 0; i < n; ++i) scanf("%d %d", &s[i].l, &s[i].r);
    printf("右端点升序 %d\n", run(s, 0));
    printf("左端点升序 %d\n", run(s, 1));
    printf("区间长度升序 %d\n", run(s, 2));
    return 0;
}

示例输出：

右端点升序 2
左端点升序 1
区间长度升序 1

三个数字摆在同一个输入上，优劣一目了然。

怎么系统地构造反例

凭空想反例基本靠运气，我自己试过，成功率很低。有一套更可靠的做法：

第一步：写出小规模的暴力解。 对 $n \le 4$ 的所有可能输入穷举，把贪心结果和最优结果逐一对拍。$n$ 小的时候，合法输入的数量是可控的，可以穷举完整个输入空间，而不是随机采样。

第二步：找到第一个反例后，缩小它。 删掉反例里不影响结论的元素，直到不能再删。最小反例往往能直接揭示失败的机理。前面三个案例里，最小的反例分别是 1 个面额组合、3 件物品、4 个区间。

第三步：看失败的那一步，问”这个判断忽略了什么”。 是自己定的规则衡量了错误的量（”最大面额”忽略剩余空间），还是规则衡量的量对但约束让它失效（”单位价值”遇到不可分割的约束）。这两种失败的修法完全不同。

第四步：如果一直找不到反例，转向证明。 但要记住，”没找到”不是”不存在”的证据。找反例的覆盖面必须说清楚——是在 $n \le 4$ 上穷举完了，还是在随机数据上试了几千组，这两种说法的证明力差别很大。

反例与证明的分工

最后把这一章和第四章的关系理一下：

	反例	证明
能证明什么	策略错误	策略正确
覆盖面	单个输入	全部输入
成本	低（构造 + 验证）	高（需要找到正确的不变量）
用在哪里	筛选阶段	确认阶段

工程上的顺序应该是：先用反例快速否定掉一批候选策略，再对剩下的策略做证明。 反过来做（先花大力气证明一个可能是错的策略）是效率最低的路径。

第八章 贪心算法与其他算法的区别

把贪心、动态规划、暴力枚举、分治放在一起比，最常见的说法是”贪心只看当前，动态规划看全局”。这个说法既不准确，也没法指导决策——它没有说明为什么一个能看全局、一个只能看当前，也没有说明在具体问题上该选哪个。

这一章从四个更本质的角度来对比：状态、决策、可证明性、代价。

从状态和决策看差别

先定义两个概念。在求解过程中，状态是对”当前已做的选择”的完整描述；决策是从一个状态转移到下一个状态的动作。

四种算法在这两件事上的处理方式完全不同：

暴力枚举：把决策序列的可能取值全部展开。状态是”已经做了哪些决策”，决策是”下一个决策取什么值”。它不做任何剪枝或合并，因此正确性无需论证，代价是状态空间可能呈指数规模。

贪心：只保留一个状态。每步做完决策后，旧状态被丢弃，新状态只由那一个贪心选择决定。它不保留任何备选状态——这是它快的根本原因，也是它可能出错的根本原因：如果贪心的那一步选错了，它没有别的路可走。

动态规划：保留所有”本质不同”的状态，但把”等价”的状态合并。它的核心操作是状态合并——把大量决策序列归并到若干个状态上，每个状态记录一个最优值。所以它既避免了暴力枚举的指数爆炸，又不像贪心那样只留一条路。

分治：把问题拆成若干个互相独立的子问题，分别求解后合并。它的关键假设是子问题之间没有交叉约束。一旦子问题互相依赖（比如区间重叠），分治就会失效。

用一句话概括四者的关系：

• 暴力枚举：不合并任何状态
• 动态规划：合并状态，保留最有价值的那一组
• 贪心：合并到只剩一个状态
• 分治：不合并状态，但保证子问题互不相干

从这个角度可以理解一个常见的现象：贪心是动态规划的一种极端特例。如果一个问题在动态规划中每个阶段的最优状态恰好唯一（无论前面怎么选，当前的最优状态都一样），那么动态规划就退化成贪心。反过来说，如果一个问题的不同决策路径会导致不同的最优状态，贪心就没有办法把这些状态压缩成一个。

从正确性证明看差别

四者需要证明的东西完全不同：

算法	需要证明什么	证明的难点
暴力枚举	枚举空间覆盖了所有解	一般不难，只需确认没有遗漏
贪心	每个局部选择是安全的（存在最优解包含它）	最难，需要交换论证或结构定理
动态规划	状态定义正确 + 转移方程正确 + 无后效性	中等，需要验证状态包含了做决策所需的全部信息
分治	子问题独立 + 合并操作正确	中等，难点在于证明子问题确实独立

贪心是四者中证明负担最重的。它的正确性不能从算法的结构上推出来——“每次都挑最好的”这个结构本身不能保证最优。这一点和动态规划不同：动态规划只要转移方程写对了，正确性就是自动成立的（因为它本质上是在穷举所有状态上的最优值）；而贪心的正确性必须额外论证。

这也是为什么第七章的反例分析和第四章的证明是配套的：贪心是唯一一种”必须先用证明换取使用资格”的算法。

从代价看差别

设问题规模为 $n$，各算法的典型代价：

算法	时间	空间	状态数
暴力枚举	$O(b^n)$ 或 $O(n!)$	$O(n)$	指数
贪心	通常 $O(n \log n)$	$O(1)$ 或 $O(n)$	常数（1 个）
动态规划	$O(\text{状态数} \times \text{转移代价})$	$O(\text{状态数})$	多项式
分治	$O(n \log n)$ 或由主定理决定	$O(\log n)$ 递归栈	不适用

贪心的空间优势常常被低估。因为它只需要维护一个当前状态，辅助空间通常是 $O(1)$，而动态规划的空间是 $O(\text{状态数})$。在状态数很大的问题上（比如背包问题里容量到 $10^9$），这个差别可能是”能跑”和”跑不了”的区别。

对比案例：两种背包

这是最能说明问题的一组对比。两个问题的题面只差一句话。

问题 A（分数背包）：物品可以切开，装一部分也行。
问题 B（0/1 背包）：物品只能整件装或不装。

问题 A 用贪心，且可证明最优。

设物品 $i$ 的重量是 $w_i$、价值是 $v_i$，单位价值 $d_i = v_i / w_i$。把物品按 $d_i$ 降序排列，依次尽量装。

正确性证明（交换论证）：设贪心解为 $G$，任意最优解为 $S$。设 $i$ 是第一个被贪心选中、但在 $S$ 中装得比 $G$ 少的物品（若不存在，说明 $G$ 装得不比 $S$ 少，已证完）。

因为贪心按单位价值降序处理，$S$ 在重量相同的情况下少装了 $i$，说明 $S$ 把这段重量分给了某个单位价值不超过 $d_i$ 的物品 $j$（$j$ 排在 $i$ 之后）。把 $S$ 中 $j$ 的一部分重量挪给 $i$：

$$\Delta = \text{挪动的重量}, \quad \Delta \cdot \mathrm{OPT} = \Delta \cdot (d_i - d_j) \ge 0$$

因为 $d_i \ge d_j$，交换后目标值不变差，且可行性不变（总重量没变）。反复应用，可以把 $S$ 变成 $G$，所以 $G$ 也是最优解。$\blacksquare$

关键在于：交换时只需要挪”一部分重量”，因为物品可以切开。 这个操作让交换论证变得非常干净。

问题 B 用动态规划，贪心失效。

同样按单位价值降序贪心，在第七章的例子上已经看到：贪心得到 160，最优是 220。

为什么 A 的证明在 B 上不成立？看那句关键操作：”把 $S$ 中 $j$ 的一部分重量挪给 $i$”。在 B 里，物品不能只装一部分，所以这个操作做不到。可行的替换只能是”整件换整件”，而整件之间的重量差不一致，交换后总重量会变，可行性不成立。

这就是 0/1 背包必须用动态规划的真正原因——不是”贪心看得太近”，而是交换论证依赖的”连续可调”这个前提没有了。

B 的动态规划解法：

设 $f[i][c]$ 表示”只考虑前 $i$ 件物品、容量为 $c$ 时的最大价值”。转移方程：

$$f[i][c] = \max\big(f[i-1][c],\ f[i-1][c - w_i] + v_i\big) \quad (c \ge w_i)$$

两个选项分别是”不装第 $i$ 件”和”装第 $i$ 件”。用滚动数组可以把空间压到 $O(W)$：

// @Moxin1044 2026-10-15
// 0/1 背包：与分数背包只差"物品不可分割"一条，但贪心会失败，必须用 DP。
// 输入：n W；随后 n 行 w_i v_i
// 输出：第一行是"按单位价值贪心"的结果，第二行是 DP 的最优解
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

struct Item { int w, v; };

int main() {
    int n, W;
    if (scanf("%d %d", &n, &W) != 2) return 0;
    vector<Item> it(n);
    for (int i = 0; i < n; ++i) scanf("%d %d", &it[i].w, &it[i].v);

    // 贪心：按单位价值降序，装得下就装，装不下就跳过（不能分割）
    auto g = it;
    sort(g.begin(), g.end(), [](const Item& a, const Item& b) {
        return (long long)a.v * b.w > (long long)b.v * a.w;
    });
    int cap = W, greedy = 0;
    for (const Item& x : g)
        if (x.w <= cap) { cap -= x.w; greedy += x.v; }

    // DP：f[c] = 容量 c 下的最大价值
    vector<int> f(W + 1, 0);
    for (int i = 0; i < n; ++i)
        for (int c = W; c >= it[i].w; --c)      // 倒序，保证每件物品最多用一次
            f[c] = max(f[c], f[c - it[i].w] + it[i].v);

    printf("贪心 %d\n", greedy);
    printf("DP   %d\n", f[W]);
    return 0;
}

示例输入（与第七章案例二相同）：

3 50
10 60
20 100
30 120

示例输出：

贪心 160
DP   220

注意 DP 内层循环必须是倒序遍历容量。正序会让同一个物品被重复使用，那就变成了完全背包。这个细节在第十章还会提到。

决策清单

遇到一个问题时，可以按下面的顺序判断：

第一步：这个问题的局部选择，能不能被证明是安全的？
能直接找到证明（或已知的结构定理）→ 用贪心。
不能，但看起来每个决策都会影响后续 → 考虑动态规划。

第二步：子问题的解能不能”合并”出原问题的解？
能，且子问题之间有重叠 → 动态规划。
能，且子问题互相独立 → 分治。

第三步：状态数有多少？
状态数在可接受范围内 → 动态规划。
状态数爆炸，但问题规模很小 → 暴力枚举（配合剪枝或记忆化）。

第四步：贪心和动态规划都可行时选哪个？
选贪心。它的时间常数更小、空间更省、代码更短。前提是证明必须成立。

第五步：贪心找不到证明，动态规划状态数又爆炸怎么办？
考虑近似算法或启发式。这是另一个话题了，但值得知道的是：贪心失效时，它往往仍是一个不错的近似。0/1 背包的”按单位价值贪心”最坏情况下能保证达到最优解的约 1/2（具体界取决于版本），这在状态数太大、精确解不可行时是有实用价值的。

第九章 时间复杂度与空间复杂度分析

贪心的复杂度分析有很强的规律性。绝大多数贪心算法的时间由两部分构成：排序（或建堆）和扫描（或反复取堆顶）。把这两部分的代价分别算清楚，再相加，几乎就能得到全部结论。

这一章把每种操作的代价来自哪里解释清楚，然后对两个前文的算法做完整推导。

排序：$O(n \log n)$ 的来源

比较排序的代价下界是 $O(n \log n)$。这个下界来自信息论：$n$ 个元素有 $n!$ 种排列，用”比较”这个只有两种结果的操作区分它们，最坏情况下需要至少 $\lceil \log_2(n!) \rceil$ 次比较；由斯特林公式 $\log_2(n!) = \Theta(n \log n)$。

常见实现的代价：

实现	平均	最坏	额外空间	稳定性
std::sort	$O(n\log n)$	$O(n\log n)$	$O(\log n)$	不稳定
std::stable_sort	$O(n\log n)$	$O(n\log^2 n)$	$O(n)$	稳定
计数排序	$O(n + k)$	$O(n + k)$	$O(n + k)$	稳定

这里要强调一点：这个 $O(n \log n)$ 是”只能比较大小”这个限制带来的。 如果键值是 $[0, k)$ 范围内的整数且 $k$ 不大，计数排序可以做到 $O(n + k)$，在 $k = O(n)$ 时就是 $O(n)$。很多贪心题的数据范围允许这种优化。

不过要注意，用计数排序替换 std::sort 通常会降低代码的可读性和通用性，而且常数因子未必更小。除非排序确实是性能瓶颈，否则没必要换。

优先队列：每次操作 $O(\log n)$ 的来源

二叉堆是一棵完全二叉树。完全二叉树有两个性质：

1. 高度是 $\lfloor \log_2 n \rfloor$。因为第 $k$ 层最多有 $2^k$ 个节点，$n$ 个节点的高度 $h$ 满足 $2^h \le n < 2^{h+1}$，所以 $h = \lfloor \log_2 n \rfloor$。
2. 可以用数组紧凑存储，下标 $i$ 的孩子是 $2i$ 和 $2i+1$，不需要指针。

堆的三种核心操作：

• top()：返回数组第 0 个元素，$O(1)$。
• push(x)：把 $x$ 放到数组末尾，然后不断与父节点比较交换（上浮）。上浮的次数不超过树高，所以是 $O(\log n)$。
• pop()：把末尾元素移到根，然后不断与较小的孩子比较交换（下沉）。同样不超过树高，$O(\log n)$。

如果一共做 $n$ 次插入加 $n$ 次弹出，总代价是 $O(n \log n)$。

一个常被忽略的优化：如果所有元素一开始就已知（比如把整个数组建成堆），可以用自底向上的建堆（make_heap），代价是 $O(n)$ 而不是 $O(n \log n)$。原因是大多数节点都集中在底层，下沉的距离很短——精确的求和是 $\sum_{h} \frac{n}{2^{h+1}} \cdot h = O(n)$。

在哈夫曼编码里，如果一开始就把所有叶子建成堆，可以省掉 $n$ 次插入。不过总复杂度仍是 $O(n \log n)$，因为后续 $n-1$ 次合并的弹出和插入无法避免。

单次遍历：$O(n)$ 的来源

扫描一遍候选集合就是 $O(n)$。这里唯一容易出问题的地方是循环体里藏了别的操作。比如：

for (const auto& x : s)
    if (x.l >= last) {           // O(1)
        chosen.push_back(x);     // 均摊 O(1)
        last = x.r;              // O(1)
    }

这是纯 $O(n)$ 的。但如果循环体里出现了 find（并查集）、top + pop（堆）、或者内层循环，复杂度就要重新算。判断方法是：把循环体里的每个操作单独标出代价，取最大值，再乘以 $n$。

并查集：$O(\alpha(n))$ 的来源

并查集的复杂度取决于用了哪些优化：

优化方式	单次操作	$m$ 次操作总计
无优化（直接挂）	$O(n)$	$O(mn)$
只有按大小/按秩合并	$O(\log n)$	$O(m \log n)$
只有路径压缩	均摊 $O(\log n)$	$O(m \log n)$
两者都有	均摊 $O(\alpha(n))$	$O(m \alpha(n))$

$\alpha$ 是反阿克曼函数。阿克曼函数 $A(n, n)$ 增长得极快，它的反函数增长得极慢。在实际可达到的一切 $n$ 下（$n$ 远小于 $2^{65536}$），$\alpha(n) \le 4$。

所以 $O(m \alpha(n))$ 在工程意义上就是 $O(m)$，虽然理论上严格大于 $O(m)$。这里要小心一个常见的表述错误：”并查集是 $O(1)$ 的”——严格地说它是 $O(\alpha(n))$，只是因为 $\alpha(n) \le 4$ 而常被当作常数。

只用一种优化是不够的。只有路径压缩时，单次操作的最坏情况仍可能达到 $O(\log n)$；只有按大小合并时也是 $O(\log n)$。必须两者都用，才能达到 $\alpha(n)$。这是并查集实现里最常见的性能缺陷。

辅助空间与输入存储空间

分析空间时要把两笔账分开：

• 输入存储空间：程序必须一直拿着的数据。比如排序问题的数组、图的邻接表。这部分通常是 $O(n)$ 或 $O(n + m)$，无论算法怎么写都需要。
• 辅助空间：算法额外开辟的临时变量。

一个常见的不严谨表述是”这个贪心算法空间复杂度 $O(1)$”，但它其实开了一个 $O(n)$ 的数组来存答案。如果这个数组是必须输出的，那它应该算进总空间。

严格的写法是：

$$\text{总空间} = \underbrace{O(n)}_{\text{输入}} + \underbrace{O(n)}_{\text{输出}} + \underbrace{O(1)}_{\text{辅助}}$$

比如区间调度那题：输入区间数组是 $O(n)$，输出选中的区间列表是 $O(n)$，辅助变量只有 last 和循环变量，是 $O(1)$。说”辅助空间 $O(1)$”是对的，说”总空间 $O(1)$”就错了。

如果不需要输出具体方案（只要答案数值），可以把选中的区间直接计数而不保存，这时总空间降到 $O(n)$。

最坏情况分析

贪心算法的复杂度通常对输入分布不敏感（因为排序和堆操作都是确定的），但有几处值得注意：

• 提前退出的条件可能不触发。Kruskal 里”选满 $n-1$ 条边就结束”这个优化在连通图上是必然触发的，但如果图不连通，循环会扫完所有 $m$ 条边。分析最坏情况时要考虑这个分支。
• 循环里的早退判断依赖输入。比如”如果当前区间与已选的最后一个不重叠就选它”——如果所有区间都重叠，每次都要做一次判断，但还是 $O(n)$，没有影响。真正的风险是循环体里嵌套了依赖输入的分支结构。
• 整数范围的隐式代价。用 long long 而不是 int 会让常数变大（一般 1.5 倍到 2 倍），但不改变复杂度。在时间限制很紧的题目上，这个常数差有时是决定性的。

完整推导一：Kruskal 算法

时间：

$$T = \underbrace{O(m \log m)}_{\text{排序}} + \underbrace{O(m \cdot \alpha(n))}_{\text{并查集}} + \underbrace{O(m)}_{\text{扫描}} + \underbrace{O(n)}_{\text{初始化并查集}}$$

逐项说明来源：

• 排序：对 $m$ 条边排序。用 std::sort 是 $O(m \log m)$。这一步是主导项。
• 并查集：对每条边做两次 find（在 unite 内部），最坏情况下每条边都要检查一次，共 $O(m)$ 次 find 和最多 $n-1$ 次成功的 unite。两者都用优化时总代价是 $O(m \alpha(n))$。
• 扫描：一次线性遍历，$O(m)$。
• 初始化：给 $n$ 个元素设父节点，$O(n)$。

取主导项：

$$T = O(m \log m)$$

因为 $\log m$ 和 $\alpha(n)$ 相比增长得快得多，$m \log m$ 总是支配 $m \alpha(n)$（除非 $m$ 极小）。

空间：

$$S = \underbrace{O(m)}_{\text{边数组}} + \underbrace{O(n)}_{\text{并查集}} + \underbrace{O(n)}_{\text{选中的边}} = O(n + m)$$

如果要进一步省空间，可以只在遍历时累加总权值而不保存选中的边，把第三个 $O(n)$ 去掉。但那样就无法输出具体方案了。

完整推导二：哈夫曼编码

时间：

$$T = \underbrace{O(n)}_{\text{建堆/读入}} + \underbrace{O(n \log n)}_{\text{合并}} + \underbrace{O(n)}_{\text{遍历输出编码}}$$

• 读入与建堆：读 $n$ 个字符是 $O(n)$。如果用逐个 push 建堆，这部分是 $O(n \log n)$；用自底向上的 make_heap 则是 $O(n)$。
• 合并：$n - 1$ 轮，每轮 2 次 pop 加 1 次 push，每次 $O(\log n)$。共 $O(n \log n)$。
• 输出编码：从根遍历一遍，每个节点访问一次。注意编码字符串的拼接：代码里用的是 code + "0"，每次拼接都要复制整个字符串，长度是 $O(\text{深度})$。最坏情况下树退化成链，深度是 $O(n)$，总代价会变成 $O(n^2)$。用 string 的引用传递或者提前把编码存成父子指针再回溯，才能避免这个问题。

这是本节里最值得注意的一处：主算法是 $O(n \log n)$，但如果输出部分写得随意，整体复杂度会被输出拖到 $O(n^2)$。

空间：

$$S = \underbrace{O(n)}_{\text{节点池}} + \underbrace{O(n)}_{\text{堆}} + \underbrace{O(n)}_{\text{栈和结果}}$$

节点池：初始 $n$ 个节点，每次合并加 1 个，最终 $2n - 1$ 个，是 $O(n)$。
堆：最多同时 $n$ 个元素。
栈：手写栈最深 $O(n)$。
结果：$n$ 个编码，总长度 $O(n \times \text{平均深度})$，最坏 $O(n^2)$。

复杂度优化与实际运行效率

最后提醒一件事：复杂度是增长率的比较，不是运行时间的比较。

两个都是 $O(n \log n)$ 的实现，实际运行时间可能差好几倍。原因是：

• 常数因子：堆操作涉及数组随机访问，缓存命中率比顺序扫描差得多。
• 数据规模：$n = 100$ 时，$O(n^2)$ 的算法可能比 $O(n \log n)$ 的更快，因为后者的常数和间接寻址开销更大。分界点通常在几百到几千之间，取决于具体实现。
• 内存层次：同样的复杂度，顺序访问比随机访问快得多。

实践上的建议是：先用复杂度筛掉渐近意义上不行的算法，再在剩下的里面用常数和对数据的适配度做选择。 不要仅凭复杂度表达式就断定”这个一定更快”——这一点在题目规模刚好卡在临界点附近时尤其重要。

第十章 贪心算法的常见错误与调试方法

这一章汇总实际编程里最容易踩的坑，每一条都给出现象和排查思路。现象是用来识别问题的，排查思路是用来定位问题的。

10.1 贪心规则缺乏严格证明

现象：小数据上过了，随机数据也过了，但提交后在某些测试点上结果偏大或偏小。

排查思路：这类问题最难定位，因为代码本身没有 bug。我踩过几次之后总结出来的检查方式是：

1. 写一个暴力解，在 $n \le 5$ 上穷举整个输入空间对拍，而不是随机采样。穷举能覆盖到随机采样很难碰到的边界组合。
2. 把贪心规则写成一句话，然后问自己：”这句话的证明写出来了吗？”如果写不出来，就要怀疑。
3. 特别检查那些”看起来显然”的地方。经验上，最容易被跳过证明的恰恰是看起来最显然的规则。

10.2 排序方向写反

现象：结果系统性地偏向一边——要么选得太多，要么选得太少，但格式都是对的。

排查思路：把输入缩到 $n = 3$，手动走一遍，看选中的元素和预期是否一致。

这类错误的隐蔽性在于”方向反了但结果还是合法的“。比如区间调度里如果误写成按右端点降序，程序照样能跑、照样能输出一堆不重叠的区间，只是数量少了。它不会崩溃，也不会输出非法数据。

一个防御手段：在代码注释里写明排序方向对应证明里的哪一句话。写代码时顺便核对一次，比事后调试便宜得多。

10.3 排序依据与证明过程不一致

现象：和 10.2 类似，但更难发现——因为排序的关键字看起来”差不多”。

排查思路：举一个具体的例子。例如证明里用的是”右端点升序”，代码里若写成”左端点升序”，用 $[0,10], [1,4], [4,8], [3,5]$ 这组输入跑一遍，会得到 1 而不是 2（第七章案例三）。构造这种”能区分两种规则”的输入是对拍时最有效的手段。

根本的防御：代码里的比较函数和证明里的判据应当逐字对应。证明写的是 $r_a < r_b$，代码就该写 a.r < b.r，不要在这一步做任何”等价改写”。

10.4 忽略相同权值的情况

现象：结果不稳定——同样的输入，多次运行结果不同；或者在不同编译器/平台上结果不同。

排查思路：检查比较函数是否满足严格弱序。C++ 标准要求的严格弱序是：

• 不自反：cmp(a, a) 必须为 false
• 非对称：cmp(a, b) 和 cmp(b, a) 不能同时为 true
• 可传递：cmp(a,b) && cmp(b,c) 蕴含 cmp(a,c)

最容易违反的是第一条和第二条，典型错误是写成 return a.x <= b.x; 或者 return a.x - b.x <= 0;。

当两个元素的键值相等时，比较函数必须返回 false（两者互不小于）。违反这条会导致 std::sort 越界访问数组——这是未定义行为，可能崩溃，也可能静默地产生错误结果。

当题目要求唯一答案时，还需要给比较函数加上次要关键字，让相等元素之间也有确定顺序。比如哈夫曼编码要求”字典序最小的方案”时，堆的比较函数要加上”下标小者优先”。

10.5 错误处理边界条件

现象：绝大多数测试点通过，但个别的（通常是 $n=1$、全相同、极值）出错。

排查思路：准备一组固定的边界输入，每次改完代码都跑一遍。建议至少覆盖：

• $n = 0$ 和 $n = 1$
• 所有元素的值相同
• 所有元素的值构成严格递增/递减序列
• 极值（最大坐标、最大权重、最小权重）
• 所有元素都会互相冲突（比如所有区间都重叠）

几个具体的坑：

• 初始化哨兵值用 -1 而不是足够小的负数。如果坐标可以为 0，-1 会让第一个元素被误判为不兼容。区间调度里 last 的初值应该取小于所有坐标的数。
• while (pq.size() > 0) 之后直接 pq.top()。pop() 让堆变空后再访问 top() 是未定义行为。
• 循环边界写成 i <= n 而不是 i < n，导致越界。

10.6 优先队列的排序方向使用错误

现象：结果完全反了（该选最多的变成了选最少）。

排查思路：C++ 的 priority_queue<int> 默认是大顶堆——top() 返回最大值。要取最小值必须显式指定比较器：

// 大顶堆（默认）：top() 是最大值
priority_queue<int> maxHeap;

// 小顶堆：top() 是最小值
priority_queue<int, vector<int>, greater<int>> minHeap;

自定义结构体时，比较器的语义也容易搞反：

struct Job { int d; long long p; };
// 下面的比较器让"收益小的"排在堆顶（小顶堆）
auto cmp = [](const Job& a, const Job& b) { return a.p > b.p; };
priority_queue<Job, vector<Job>, decltype(cmp)> pq(cmp);

这里的 > 是反直觉的：写 > 得到的是小顶堆，写 < 得到的才是大顶堆。原因是 priority_queue 内部用的是”堆顶是最不符合比较关系的元素”这个约定。记不住的时候，写个小程序打印三次 top() 验证一下。

10.7 整数溢出

现象：在数据范围较大的测试点上答案变成一个奇怪的负数或小正数。有时候小数据完全正确。

排查思路：

1. 估算最大可能值。把每个乘法、每个累加的最大值都算一遍。例如 $n = 10^5$ 个元素、每个最大 $10^9$，总和最大 $10^{14}$，而 int 的上限约 $2.1 \times 10^9$，必然溢出。
2. 中间结果也要算。最容易被忽略的是比较函数里的交叉相乘：a.v * b.w 中两个数各是 $10^9$，乘积是 $10^{18}$，需要 long long（上限约 $9.2 \times 10^{18}$）。如果数据再大一点，long long 也不够，要用 __int128。
3. 累加时确认类型。total += a[i] 里如果 total 是 int，即使 a[i] 是 long long，结果也会被截断。累加变量本身的类型必须是宽类型。
4. 打印时用对格式符。long long 要用 %lld，写成 %d 会输出错误的值（在 64 位 Linux 上表现为只取了低 32 位）。

一个实用的习惯：除了循环下标，其他数值变量一律用 long long。 在现代 64 位环境下，long long 的运算速度和 int 相差很小，为了省这点开销而冒溢出的风险不划算。

10.8 把局部最优误认为全局最优

现象：算法逻辑自洽，代码没有 bug，复杂度也对，就是答案错了。

排查思路：这是第七章的主题。检查方式就是构造反例：

1. 从最小规模开始穷举。$n=3$ 或 $n=4$ 时，输入空间通常是可控的，可以完全穷举。
2. 找到反例后，把它缩小到最小。最小反例往往能说明失败机理。
3. 如果确实找不到反例，再去写证明——而不是直接认定它是对的。

10.9 错误地把某个经典问题的策略套用到其他问题

现象：在两个”看起来很像”的问题上用了同一套代码，其中一个过了，另一个没过。

排查思路：找出两个问题的约束差别，然后检查证明里的哪一步用到了这个差别。

最典型的例子是两种背包：分数背包和 0/1 背包。代码几乎一样（都是按单位价值排序然后顺序取），差别只在”取不下时能不能拿一部分”。但这一条差别让分数背包的交换论证失去基础（第八章），于是 0/1 背包必须改用它法。

检查清单：

• 物品能否分割？
• 端点相接算不算冲突？
• 是否允许相同的键值？
• 约束是”硬”的（必须满足）还是”软”的（尽量满足）？
• 是”最多选 $k$ 个”还是”恰好选 $k$ 个”？

每一项差别都要单独验证一遍证明是否仍然成立。

10.10 复杂度无法满足数据范围要求

现象：算法正确，小数据通过，大数据超时。

排查思路：先按数据范围估算需要的复杂度。经验标准（假设 1 秒时限）：

复杂度	可处理规模 $n$
$O(n!)$	$\le 10$
$O(2^n)$	$\le 25$
$O(n^3)$	$\le 500$
$O(n^2)$	$\le 5000$
$O(n \log n)$	$\le 10^6$
$O(n)$	$\le 10^7$

如果估算出的复杂度和数据范围不匹配，先换算法而不是优化常数。

逐项检查复杂度的来源：

1. 排序是不是 $O(n \log n)$？有没有在循环里反复排序（那就变成 $O(n^2 \log n)$）？
2. 循环体里有没有隐藏的线性操作？比如在遍历时调用 find（并查集，均摊 $O(\alpha)$，可以接受），或者调用 count、find（线性查找，不可接受）。
3. 有没有在循环里做 vector 的 insert 或 erase（$O(n)$）？这类操作会让整体复杂度悄悄升一阶。
4. 字符串拼接是不是在循环里持续进行（每次复制整个字符串）？这在哈夫曼编码的输出环节是真实存在的陷阱（第九章）。

调试流程小结

把上面的内容组织成一个可执行的调试顺序：

第一步：验证正确性，不验证性能。 用一个 $n \le 6$ 的暴力解对拍。先穷举小输入空间，再随机大规模采样。

第二步：如果对拍不一致，先看是不是规则错了，再看是不是代码错了。 做法是把反例的输入手动走一遍贪心流程，和代码的输出对比。如果手动走的结果和代码不同，是代码 bug；如果相同但和暴力解不同，是规则错了。

第三步：如果对拍一致，检查边界。 用 10.5 里列的那组边界输入跑一遍。

第四步：如果都对，看性能。 按 10.10 的方法估算复杂度，找到瓶颈代码。

第五步：注意数据类型的边界。 在最大数据上跑一次，看有没有溢出。

这套顺序的核心是”先证明规则对，再证明代码对，最后证明性能够“。顺序反了会浪费大量时间——比如花两小时优化一个本来就错的算法的性能。

第十一章 如何系统学习贪心算法

贪心的学习曲线有个特点：入门很快，但”能自己判断一个策略对不对”这一步很难跨过去。前面几章讲清楚了方法，这一章给出一条循序渐进的练习路线。

第一阶段：排序与局部选择

目标：熟悉”排序后扫一遍”这个最基本的形态，建立”贪心 = 有序 + 不回头”的直觉。

需要掌握的概念：

• 比较函数怎么写（严格弱序的三个要求）
• 排序关键字和目标函数的关系
• 贪心与模拟的区别（贪心只做一次决策，模拟会反复演算）

适合练习的问题类型：

• 单关键字的排序贪心（按最大值、按最小值、按比值）
• “选尽量多的不冲突元素”这一类
• 简单的资源分配（把任务分给机器使最大负载最小）

这个阶段不需要证明。 先用直觉建立手感，把常见形态见够。

第二阶段：区间调度与交换论证

目标：掌握交换论证，学会从目标函数推导排序规则。

需要掌握的概念：

• 邻项交换法（第三章 3.3 节的推导模板）
• 交换论证的两个必做步骤（可行性 + 目标值）
• 为什么”相邻”这个限制让论证变得可行

适合练习的问题类型：

• 区间调度（三种排序规则的对比，第七章案例三）
• 区间点覆盖（第四章 4.3 节）
• 排队类问题（排队接水、以及需要交叉相乘比较的双关键字版本）
• 通过邻项交换推导出非平凡排序规则的问题

这个阶段的标志性能力：拿到一个带两个属性的排序问题，能自己推出判据，而不是搜”这个题怎么排序”。

第三阶段：优先队列与后悔贪心

目标：掌握”动态候选集合”这一类问题。

需要掌握的概念：

• 堆的时间复杂度（为什么是 $O(\log n)$）
• 大顶堆和小顶堆的写法
• 后悔贪心的结构：先接受、检测约束、撤销最差
• 撤销准则必须由证明给出

适合练习的问题类型：

• 哈夫曼编码（第六章例题二）
• 带截止期的任务调度（第六章例题四）
• 合并果子一类的”反复取最小”
• 需要”撤销上一步选择”的排序问题

这个阶段的难点在例题四的证明。 我带过的进度卡在这里的人最多。它需要先建立可行性刻画，再用前缀支配的归纳。建议反复读几遍第六章那部分——它是”后悔贪心的撤销准则是怎么被证明的”的标准范例。

第四阶段：哈夫曼与最小生成树

目标：掌握两种经典方法——“贪心选择性质 + 最优子结构”的归纳证明，以及”结构定理 + 不变量”的图论证明。

需要掌握的概念：

• 哈夫曼的两个引理及其分工（第六章例题二、第四章 4.2 节）
• 割与割性质（第四章 4.5 节）
• 并查集的两种优化及其必要性

适合练习的问题类型：

• 哈夫曼编码及其变形（多路哈夫曼、带长度限制的编码）
• Kruskal、Prim
• 其他能归入拟阵框架的问题

第五阶段：独立完成证明

目标：不再依赖”背下来的结论”，能自己写出一份完整的证明。

练习方法：找一道有标准答案的贪心题，先不看题解，自己完成下面三件事：

1. 写出贪心规则
2. 尝试构造反例（至少花 15 分钟）
3. 写出一份严谨的证明，明确标出每一步用的是哪种方法（交换论证 / 归纳 / 反证 / 结构性质）

写完之后再对照题解。重点比较的不是结论是否一致，而是”证明的切入点”是否一致。 如果你的证明比题解更绕，说明还没有抓住这个问题的关键不变量的形式。

这一阶段的验收标准：你写出的证明里不能出现”显然”、”易证”、”直觉上”这三个词。

第六阶段：反例构造与边界分析

目标：能快速判断一个策略是错的，并且能构造出最小反例。

需要掌握的概念：

• 反例与证明的不对称性（第七章开头）
• 如何缩小反例
• 从最小反例反推失败机理

练习方法：

• 拿那些”看起来很像”的问题对，比如分数背包和 0/1 背包、区间调度和区间点覆盖，写出它们的差别，然后构造一个能区分两者的输入
• 对每个学过的贪心算法，试着找出它不适用的边界（比如 Kruskal 在非连通图上会怎样、哈夫曼在频次相同时的解是否唯一）

第七阶段：更抽象的理论

目标：理解”什么样的贪心一定对”这个问题的理论回答。

推荐方向：

• 拟阵。第二章末尾提到的 Rado–Edmonds 定理说的是：在拟阵上，按权值降序的贪心一定给出最大权独立集。理解这个定理之后，你会对”为什么 Kruskal 是对的”有一个完全不同的视角——它不再依赖割性质的具体证明，而是”无圈子集构成图拟阵”这个事实的直接推论。
• 贪心拟阵（greedoid）。有一类问题的最优性不能用拟阵解释，但可以用更宽松的公理系统刻画。这是拟阵理论的推广方向。
• 子模函数最大化。当目标函数是单调子模时，贪心算法有可证明的近似比（$(1 - 1/e)$ 是一个著名的界）。这在不能求得精确解时提供了理论保证。

注意：理论工具是用来解释已知事实的，不是用来替代具体证明的。哈夫曼编码、带截止期调度这些问题的最优性都不能直接由拟阵定理推出，它们的证明仍然要靠交换论证。所以这一阶段应该放在你已经能独立完成具体证明之后。

学习路线总览

阶段	核心方法	标志性能力	建议投入
一、排序与局部选择	排序 + 扫描	建立”有序+不回头”的直觉	短
二、区间调度	交换论证	能推导排序规则	中
三、优先队列与后悔贪心	堆 + 撤销	能证明撤销准则	长
四、哈夫曼与 MST	归纳 + 结构定理	能建立并维护不变量	长
五、独立证明	综合	写出无”显然”的证明	长
六、反例与边界	构造 + 对拍	快速否定错误策略	中
七、抽象理论	拟阵等	理解”什么样的贪心一定对”	按兴趣

一个提醒：这七个阶段不是严格线性的。实际学习中，第二阶段和第六阶段可以并行推进——边学交换论证，边练习构造反例，两者的能力互相促进。真正需要先行的只有第一阶段（手感）和第二阶段（交换论证的基本功）。

第十二章 总结

回到最开始那句话：贪心的规则简单到一句话就能说完，但它的可靠性需要一整套工具来保证。

核心思想：贪心把求解过程拆成一串局部决策，每个决策只看当前状态，选完不回头。它的力量来自这个”不回头”——没有回溯、没有状态爆炸，于是时间和空间都极其省。

适用的条件：需要同时具备最优子结构和贪心选择性质。前者是必要条件，后者才是真正的门槛：它要求存在一个选择规则，使得每一步的局部最优选择都能被某个最优解包含。

策略设计的方法：从目标函数的形式出发，找出影响结果的关键变量，提出候选规则，先尝试反例，再寻找证明。第三章那九步里，最容易跳过也最不能跳过的两步是”尝试构造反例”和”检查边界”。

证明的方法：交换论证、数学归纳法、反证法、安全选择、结构性质。它们在形式上不同，但都归结到同一句话上——从任意最优解出发，通过保持可行且不变差的替换，可以把它变成贪心解。

复杂度：绝大多数贪心的时间由”排序或建堆”加”扫描或取堆顶”两部分构成。分析的关键是把每一项的来源说清楚，而不是只写一个 $O(n \log n)$。空间上要把输入、输出、辅助三笔账分开算。

局限：贪心是四种常见算法思想里证明负担最重的一种。它的正确性不能从结构上推出来，必须额外论证。这带来一个实际后果——在不能完成证明的时候，贪心不是一个稳妥的选择。

所以真正掌握贪心，不是记住”区间调度按右端点排序”、”哈夫曼用最小堆”这些结论。这些结论本身很快就能查到。真正要掌握的是这四件事：

第一，能把题目写成优化目标加约束的形式。 目标写错，后面全错。

第二，能提出候选的贪心规则。 这需要见过足够多的模式（第五章的六种），也需要对目标函数的形式足够敏感。

第三，能构造反例来否定错误的规则。 这是成本最低的筛选手段，也是最少被认真练习的能力。

第四，能用严谨的证明确认剩下的那个规则。 写出的证明里不应该出现”显然”和”直觉上”——如果出现了，说明还有一步没想透。

这四件事合起来，就是从”会背贪心题解”到”能独立解决新的贪心问题”之间的全部距离。

---

参考资料

本文在写作过程中查阅并核对了下列资料：

1. OI Wiki，《贪心》 —— https://oi-wiki.org/basic/greedy/
   用于确认贪心的基本表述、交换论证与数学归纳法的定位、”排序解法”与”后悔解法”的分类，以及与动态规划的区别。

2. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. Introduction to Algorithms（《算法导论》） —— 活动选择问题的交换论证（第 16 章）、哈夫曼编码的最优性证明（第 16.3 节）、拟阵与贪心算法（第 16.4 节）、并查集的复杂度分析（第 21 章）。第四章和第六章的证明结构参考了该书的组织方式。

3. Jon Kleinberg, Éva Tardos. Algorithm Design —— 交换论证的系统化讲解、割性质与最小生成树的贪心证明、带截止期调度的可行性刻画。第四章 4.5 节的割性质证明思路来自该书对最小生成树的处理。

4. R. Rado (1957) —— 关于拟阵上贪心算法最优性的原始结论，即第二章末尾提到的 Rado–Edmonds 定理。

5. R. E. Tarjan (1975), Efficiency of a Good But Not Linear Set Union Algorithm —— 并查集在路径压缩与按秩合并同时使用时的 $O(m \alpha(n))$ 复杂度界，以及反阿克曼函数的定义。

6. USACO Training 的 Work Scheduling 问题 —— 带截止期任务调度的经典模型，本文第六章例题四采用的正是这一模型。

文中所有代码均为 C++17，在 GCC 下用 -O2 -std=c++17 -Wall 编译通过，样例输入输出均为实际运行结果。