第四部分：贪心算法

预计用时：1-2 周

贪心算法非常优雅：无需复杂的递推式，无需状态爆炸——只需一个精妙的观察，让一切迎刃而解。难点在于知道何时贪心可行，并在可行时能证明它的正确性。

涵盖的主题

学完本部分后能解决什么问题

完成第四部分后，你将能够挑战：

• USACO Bronze：

  • 带贪心决策的模拟（最优地处理事件）
  • 简单的基于排序的贪心

• USACO Silver：

  • 活动选择（不重叠区间最大化）
  • 调度问题（最早截止日期优先，最小化最大延迟）
  • 贪心 + 二分答案
  • Huffman 风格的合并问题（优先队列）

关键贪心模式

前置条件

开始第四部分前，请确认你能做到：

• 用自定义比较器排序（第 3.3 章）
• 使用 priority_queue（第 3.1 章）
• 二分答案（第 3.3 章）—— 第 4.2 章中使用

贪心思维方式

编写贪心解法前，先问自己：

1. 每一步「显然最优」的选择是什么？
2. 能做交换论证吗？ 把贪心选择与任何其他选择互换，结果只会变差（或保持不变）吗？
3. 能找到反例吗？ 试一些贪心可能失败的小例子。

若能回答 (1) 和 (2) 且对 (3) 找不到反例，你的贪心很可能是正确的。

本部分学习建议

1. 贪心最难「验证」。 不像 DP 只需要正确的递推式，贪心需要正确性论证。多练习交换论证证明的草稿。
2. 贪心失败时，DP 通常是修复方案。 硬币找零（第 4.1 章）完美地展示了这一点。
3. 第 4.2 章有真实的 USACO 题目 —— 仔细研究代码，不只是高层次的想法。
4. 贪心 + 二分搜索（第 4.2 章）是频繁出现在 Silver 的强力组合。贪心解决「检查」函数，二分查找最优答案。

💡 核心思路： 排序是大多数贪心算法的引擎，排序标准体现了「贪心选择」——优先选最好的元素。交换论证证明了这个标准是最优的。

🏆 USACO 技巧： USACO Silver 中，若题目问「在约束 Y 下最大化 X」或「达成 Z 的最小代价」，先尝试带贪心检查的二分答案。这个组合解决了相当大比例的 Silver 题目。