贪心整合包

入门贪心题目的放在 [贪心整合包（easy）](https://www.luogu.com.cn/training/140652) 里了 中等难度的题目放在 [贪心整合包（medium）](https://www.luogu.com.cn/training/145463) 里了。 **主题单**未评定难度的题都是黑及以上难度的。 题目按照洛谷难度排序，而不是按照实际难度排序。或者说这些难题之间根本没有可比性。只是为了做这些题的人不需要手动点一下按洛谷难度排序而这样做的。 贪心整合包主题单适合省选及以上水平选手练习。 贪心整合包（medium）适合提高组及以上水平选手练习。 贪心整合包（easy）适合普及组及以上水平选手练习。 介绍一下我所知的贪心吧。 最基本的，贪心就是一直选择当前最优解从而得到全局最优解。贪心总是非常高效的算法，但并不适用于所有求最优解的问题。 一般来说像字典序最大这类问题都要用到贪心思想，因为字典序完美契合贪心的定义。01 字典树求解异或最大值问题也是同理。 而有时贪心就更难被发现了，这时就要用到数学归纳法、暴力推式子等方式验证贪心的正确性。有一种比较通用的证明贪心的方法叫邻项交换法，其实就是推式子然后比大小。 大多数难的贪心题的考察点都在贪心策略的选择上，因此大力猜结论和（感性）证明贪心的正确性就成为了一个人想要做出一道难的贪心题的关键所在。往往得到正确的贪心策略后代码就很好写了。 感性猜结论往往能够猜得八九不离十，但是一道好的贪心题不应该让结论非常容易猜到。比如 [CF1601D](https://codeforces.com/problemset/problem/1601/D) 这道题（[我写了题解](https://www.luogu.com.cn/problem/solution/CF1601D)），运用了数学归纳法，证明了一个与感性猜想相悖的很离谱的（也很美丽的）结论。 既然不能猜到结论，遇到这类问题应该怎么办呢？尝试着把暴力打出来，自己想几个贪心策略，然后 hack 自己，将 hack 数据用暴力跑然后看正解是怎么得到这个最优解的，找找规律就好。 除此之外，多做贪心题一定是有助于增长视野的。一个种类的贪心题只需要做一道，其它题也就迎刃而解了。 贪心整合包三件套包含了贪心入门题到贪心难题一共 $70$ 多道题，包含了大多数常见的贪心策略和一些高妙策略。每道题我都有看过，绝大多数题我都做过，保证每道题的核心部分都是贪心，当然也有一些题要适当运用数据结构。 另外，个人认为模拟费用流就是贪心，虽然一些题就是线段树维护费用流。费用流的题是不属于贪心题的，但模拟费用流本质还是可以用贪心解释，且也符合贪心的定义，故模拟费用流的题属于贪心题。不过由于 Dijkstra 和 Kruskal 等算法虽然模板用了贪心思想，但一般题目的难点是建模，故不属于贪心题。 最后，若有做法非常高妙的贪心题欢迎私信给我说。 --- 最近看到一个有趣的问题： ``` 为什么克鲁斯卡尔算法也被算作是贪心算法？ 贪心算法的定义：“贪心算法”是指在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，算法得到的是在某种意义上的局部最优解。 我能理解kruskal找的边是“当前”最短的边，但这个当前最短的边不是全局的路径排序的来的吗？因为kruskal解决MST问题只需要考虑顶点、边、边的权重三个因素，而每每加入一条边，整个算法就向前推进一个进度（经过定点数V-1次算法结束），所以每条边除了权值差异就都是等价的。已经对全部路径的权值进行了排序难道不就是考虑了全局路径的情况，不就是从整体最优上考虑的吗？怎么还能被算作贪心算法呢？（相对的，prim算法、迪杰斯特拉算法算作是贪心算法我就觉得很合理） ``` [来源](https://www.zhihu.com/question/526333056/answer/2427783778) 这是一个很奇妙的想法，这种想法的谬误在于：把排序认为是 Kruskal 算法的一部分了。 事实上现在也有很多人认为```贪心题必须要排序```，但排序和贪心从来没有任何关系。重要的是，贪心只是一种思想，而排序只是为了降低时间复杂度。排序恰好契合了贪心一直选当前最优的思想，能够将每次重新找最优变为连续的从优到劣。堆经常被用来做贪心题亦是如此。如果一直想着“我应该按哪一维排序”或者“堆的排序关键字是什么”这种问题，而不想贪心究竟是为了什么，那就得不偿失了。