如何看出一个题有Greedy的解法

楼主目前也刷了近千题 周赛排名不太稳定有时候前800 有时候只有3-4千名。最近总结 发现一直对Greedy不是很敏感 碰上greedy很多时候看不出来。 想问问大家有没有什么理解 能够帮助到我们这些不太会利用greedy做题的人。

去codeforce上 刷一下greedy， constructive的tag。推荐难度1400 - 1800 的。

最优化问题做题的话你的选择是很有限的，抛开数学题不谈，剩下的要么就是搜，要么就是dp，要么就是二分、分治，要么就是贪心（还有建图最大流之类的以及一些奇奇怪怪的暂且不谈吧）。
这里面搜的数据范围一般比较明显，除非是花样剪枝地，另外就是基本上就没有太好的结构或者性质
二分的话要能转化成判定性问题，并且判定的复杂的够低，并且可行解是连续的。
分治、dp和贪心在性质上很接近，和分治相比后两者的特征是可以划分出阶段，而分治则需要能够高效地合并解。
有了阶段就再看它递推的过程中是更容易合并状态还是更容易直接选出下一个状态。如果是贪心的话，因为决策的时候是盲目的，所以要么决策之间有很高的独立性，要么就是你稍微算算可以发现一边损失的可以再另一边补回来，所以每次按照单位收益最高选就行，再或者就是证明如果不按照贪心的顺序的解一定不是最优的诸如此类。。（Exchange Argument、拟阵这些的）。和dp的区别就是这里每个阶段不再需要尝试多个状态。反过来说，如果用DP做可能也可以，但是效率可能就有问题，或者压根就没法进行状态编码（比如状态可能是n!的而且没法合并）
当然这里只针对相对比较简单的问题。

同疑惑，插个眼～

周赛3000-4000是只做了3题吗？

楼主贴几个不太懂的greedy的例子？ 我greedy也不行… 蹲一个讨论