贪心策略小结

NOIP考前攒rp，希望HB不要G。

有很多题目，看似是不可实现的，比如 \(5\times 10^7\) 的量级，严格处理的复杂度是 \(O(N^2)\) 或者 \(O(N\log N)\) 的。没法在合规的时间里解决，这种情况一般会在证明之后直接得到最优解——这种策略就称作贪心。
当然，也有的时候贪心是用来辅助优化复杂度的。

直接贪心

这一类的贪心往往可以直接证明最优性。

[NOIP2002 提高组] 均分纸牌

最左边的一组牌如果不是刚好的，它必然会有一次移动一次，并且之后不会再移动，所以顺着枚举当前位置是否需要移动即可。

[NOIP2004 提高组] 合并果子

Huffman树是最优的。

[NOIP2015 提高组] 斗地主

一个很直观的想法，能够一次性出很多就出很多，不会拆成单和双，所以可以优化搜索顺序做到最优性剪枝。

[CSP-S2020] 贪吃蛇

将所有的蛇按从大到小排序，记为 \(a_1,a_2\dots a_n\) ，考虑 \(a_1\) 会不会吃。
\(a_1\) 吃了蛇之后会变成 \(a_1-a_n\) ，因为 \(a_1\leqslant a_2,a_{n-1}\leqslant a_n\) ，所以 \(a_1-a_n\leqslant a_2-a_{n-1}\) ，所以 \(a_1\) 吃了 \(a_n\) 之后只要不是最后一个就不会再被吃掉，因为 \(a_2-a_{n-1}\) 会一直在它的后面。
用两个双端队列维护数组即可，只是需要特判最后一次即可。

反证法

用反证法证明策略是对的。

[NOIP2010 提高组] 关押罪犯

将所有的罪犯矛盾关系从大到小排列，最终的答案必然是第一个不能在满足两个监狱关系的囚犯。
如果不是这样情况能是答案更优，则这对囚犯也能放在不同的监狱且比它大的也都可以，与它是第一对不能满足关系的矛盾。

调整法

证明答案不断调整不会变劣，并且调整方向固定。

[NOIP2012 提高组] 国王游戏

对于某两个大臣，假设他们左右手的数分别是 \(a_i,b_i\) 和 \(a_{i+1},b_{i+1}\) ，他们前面的所有大臣的左手的树的乘积为 \(D\) 。
他们两个交换前后的贡献分别是 \(\max(\frac{D}{b_i},\frac{D\times a_i}{b_{i+1}})\) 和 \(\max(\frac{D}{b_{i+1}},\frac{D\times a_{i+1}}{b_i})\) 。
现在我们要比较它俩大小，两边同时乘 \(\dfrac{b_ib_{i+1}}{D}\) 得到 \(\max(b_{i+1},a_ib_i)\) 和 \(\max(b_i,a_{i+1}b_{i+1})\) 。
因为 \(1\leqslant a_i,a_{i+1}\) ，所以 \(b_{i+1}\leqslant a_{i+1}b_{i+1},b_i\leqslant a_ib_i\) 。
所以最终答案等价于比较 \(a_ib_i\) 和 \(a_i+1b_i+1\) ，所以 \(a_ib_i\) 较大的应该放在后面才能使答案更优。

小结

为什么贪心难，因为你看不出来它是贪心，所以需要对数据有一定的敏感性，多观察性质。