2024-2025年度的USACO竞赛12月赛季在前不久刚刚落下帷幕，也收到了不少同学晋级的喜讯，有从铜级直升金级的大神级选手，也有非满分晋级1月赛季继续冲击奖项的同学。那么在各大计算机竞赛中大家都熟知的“贪心算法”该如何使用才能帮助我们更快更好地解决问题呢？我们今天邀请到了 理科竞赛教师龚哲浩老师，来为大家讲解“贪心算法”这一解题利器！
贪心算法介绍
在USACO（美国计算机奥林匹克）等各类计算机竞赛中，贪心算法都是比较常用到的解决问题的方法，具有非常高效，编写快速的特性。我们将通过一个实际的例子对贪心算法进行讲解，并展示一道USACO竞赛真题。
以下是一个路径图，我们将找出由A到F的路径。
运用贪心算法（Greedy Algorithm）
贪心算法在每一步都选择当前最优解，希望通过局部最优解达到全局最优解。应用在此图中，可以通过以下步骤找到从A到F的路径：
1. 从起点A出发，选择A到B（权重2），因为它是A的邻接节点中权重最小的。
2. 从B出发，选择B到D（权重1），因为它是B的邻接节点中权重最小的。
3. 从D出发，选择D到F（权重4），因为它是D的邻接节点中唯一的。
4. 最终路径：A → B → D → F，总权重为7。
真题讲解
贪心算法通过始终选择当前看起来最优的选择来构建问题的解决方案。贪心算法从不回撤已做的选择，而是直接构建出最终的解决方案。正因如此，贪心算法通常非常高效。贪心并不指代某一种算法，而是指一种思维方式，它被应用于解决具体问题；没有唯一的方法来实现贪心算法。
我们参考2020年2月的铜牌第二题来理解一下贪心算法：
这是一个贪心问题。没有显而易见的暴力破解方法可供尝试；翻转不同子串的方式太多了。但如果你只尝试几个例子，手动解决它们其实相对容易。
在这个案例中，首先通过观察简化了问题，即翻转子串的顺序并不重要。关键是每头牛被翻转了多少次。因此，假设我们从左到右进行翻转（按照它们第一次被翻转的牛来排序）。
现在想象一下从左到右扫描字符串。每当发现一个不匹配时，必须立即修正它（因为我们刚才说了我们不会回头）。因此我们必须从这头牛开始翻转。翻转何时结束？只要有不匹配的牛，我们应该继续翻转，因为修正它们是不受限制的。一旦我们遇到当前匹配的牛，我们应该停止。因为如果我们翻转这头牛，下一步我们立刻又需要再次翻转它。任何有用的翻转我们都可以在刚才的步骤中一起完成。因此，继续翻转并不会帮我们节省任何步骤。
这为我们提供了一个非常简单的解决方案：只需翻转所有不匹配的牛的区间。我们可以通过一次扫描字符串来计算这些区间的数量——只需要数一下有多少位置开始不匹配就行了。
以下是该题的解题代码，大家可以进行参考
贪心算法的适用场景
最短路径问题：当图的权重为非负数时，可以使用贪心算法，它本质上是一种贪心算法。
最小生成树（如Prim和Kruskal算法）：这些算法通过贪心策略构建最小生成树。
区间选择问题：这类题目通常涉及选择尽可能多的区间或活动，同时满足区间或活动之间的冲突限制。例如，“活动选择问题”要求选择最多不重叠的活动，这里可以用贪心选择结束时间最早的活动。
货币问题：涉及最少数量的硬币凑成特定金额的题目。如果硬币面值满足贪心性（例如，通常的1元、5元、10元等面值系统），那么可以直接使用贪心算法按面值从高到低选择硬币。
【竞赛报名/项目咨询+微信：mollywei007】
