贪心算法总是选择当下看起来最优的方案，并且从不回头反悔。当它适用时，便是竞赛编程中最简单、最快速的工具之一。
对于备战 USACO（USA Computing Olympiad）等奥林匹克竞赛的学生来说，贪心技巧是一道必经的门槛。它首次正式出现在 Silver 级别，参赛者从这里开始学习诸如递归搜索和贪心策略等基础解题模式；而在 Gold 和 Platinum 级别的题目中，贪心也会与其他思路结合出现。理解何时"每一步都抓取最优选项"才能真正得出全局最优答案，正是区分严谨选手与运气型选手的一项能力。
是什么让一个算法成为"贪心"？
贪心算法逐步构建解决方案，每次都选择能带来最直接收益的下一步，而不重新考虑此前的选择。这与动态规划不同，后者会探索多种选择的组合。贪心更快且占用更少内存，但只有当问题具备恰当结构时，它才能给出正确答案。
两条性质使贪心方法成立：
- 贪心选择性质：局部最优的选择总能成为某个全局最优解的一部分。
- 最优子结构：整个问题的最优解包含其子问题的最优解。
若两者都成立，贪心便有效。若不成立，贪心可能得出一个看似合理却错误的答案，而这正是许多初学者在竞赛中落入的陷阱。
值得掌握的经典问题
少数几道教科书式的问题几乎涵盖了你在竞赛场景中所需的每一种贪心模式：
- 区间调度（活动选择）：要选出最多数量的互不重叠区间，可按结束时间排序，然后反复选取仍能放入的最早结束的区间。先排序是 USACO Silver 中最常见的贪心套路。
- 分数背包：按价值与重量之比排序，优先选取单位价值最高的物品，必要时分割最后一件物品。注意，物品不能分割的 0/1 版本则需要改用动态规划。
- Huffman 编码：反复合并出现频率最低的两个符号以构建最优前缀编码，这是一种在真实数据压缩中使用的贪心方法。
需要记住的模式：大多数竞赛贪心题都以排序开始。问问自己"按什么关键字排序？"——结束时间、比率、截止期限还是大小——其余的解法往往随之而来。
证明贪心是正确的
这正是学生们会跳过的部分，而它会让他们丢分。贪心思路必须经过论证，而不能仅仅因为样例通过就提交。最可靠的工具是交换论证。
假设某个最优解与贪心解不同。找到它们第一处产生分歧的地方，然后证明换入贪心选择不会使解变得更差。如此反复，最优解便能在不损失质量的前提下转化为贪心解，因此贪心也必定是最优的。
其他有用的技巧包括数学归纳法和反证法。即使是简短的书面论证，也能帮助你在评测系统之前发现反例。当你无法证明正确性时，应将其视为一个警示信号：贪心可能是错误的工具，需要改用动态规划或搜索。
如何练习
- 先用暴力法解决一道题，然后寻找贪心捷径并证明二者结果一致。
- 在编码之前，始终尝试为自己的贪心思路构造一个反例。
- 记录是哪个排序关键字攻破了每道题；久而久之，你就能瞬间识别出模式。
USACO 在一个赛季中会举办数场比赛，每场都给参赛者数小时的时间窗口，在所属分组（Bronze、Silver、Gold 或 Platinum）中完成一小组题目。赛制、参赛资格和时间安排可能逐年变化，因此在报名前请查阅官方 USACO 信息以获取最新详情。
贪心思维奖励那些审慎推理而非凭空猜测的学生。如果您的孩子喜欢这种结构化的解题方式，BIAA 的竞赛编程项目将引导有志向的中小学生从第一道"排序加选择"的题目，一路走向高阶的奥林匹克竞赛备战。探索 BIAA，找到合适的起点。