在NO C大赛的备考冲刺阶段（考前4周），贪心算法中的优化技巧是我们需要重点攻克的内容，尤其是通过真题案例总结贪心策略正确性证明的常用方法与思维路径这一板块。
一、贪心算法概述
贪心算法是一种在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择，从而希望导致结果是全局最好或最优的算法。比如在找零钱的问题中，我们总是优先选择面额较大的货币来凑出目标金额。
二、贪心策略正确性证明的重要性
在比赛中，仅仅使用贪心算法得到一个结果是不够的，我们需要证明这个贪心策略是正确的。只有证明了其正确性，才能确保我们的答案是可靠的，得分也是有效的。
三、真题案例中的常用方法
- 数学归纳法
- 知识点内容：先证明对于某个初始规模的问题（如最小的输入规模），贪心策略能得到最优解。然后假设对于规模为n的问题，贪心策略正确，再推导出对于规模为n + 1的问题，贪心策略同样正确。
- 学习方法：多做一些简单的递推关系的数学归纳法练习题。比如对于数组排序中的一些贪心策略，从最简单的只有一个元素的数组开始，逐步增加元素个数去理解和运用归纳法。
- 交换法
- 知识点内容：假设存在一个最优解不是按照贪心策略得到的，然后尝试在这个最优解中交换一些元素或者步骤，使其更接近贪心策略的结果，并且证明这样交换后的解不会比原来的最优解差。
- 学习方法：分析一些关于任务调度方面的真题案例。例如，有多个任务在不同机器上执行，有不同的执行时间和截止时间，通过假设一个非贪心的任务分配方案，然后用交换法去对比它和贪心方案的结果。
- 反证法
- 知识点内容：假设贪心策略得到的不是最优解，然后从这个假设出发推导出矛盾的结果。
- 学习方法：在一些图论相关的贪心算法真题中练习，如最小生成树的构建。假设构建的最小生成树不是按照贪心策略得到的最优解，然后找出这个假设与已知条件或者图的性质之间的矛盾。
四、思维路径总结
- 深入理解问题本质
- 在面对每个真题案例时，要先明确问题的目标是什么，是要最大化利润、最小化成本还是其他目标。只有清楚了目标，才能确定合适的贪心策略。
- 分析局部与全局关系
- 贪心算法是基于局部最优选择达到全局最优。要思考每个局部的选择如何影响整体结果，并且在证明过程中也要体现这种关系的合理性。
- 多维度思考
- 不要局限于一种证明方法。有时候一个真题案例可以用多种方法来证明贪心策略的正确性，尝试从不同角度去思考可以加深对问题的理解。
在最后的冲刺阶段，考生们要多研究真题案例，熟练掌握这些贪心策略正确性证明的常用方法和思维路径，提高自己在NOC大赛中的竞争力。
喵呜刷题：让学习像火箭一样快速，快来微信扫码，体验免费刷题服务，开启你的学习加速器！
