贪心训练 1
2026-08-27
前情提要 没错我在上个赛季场上一道贪心都没做出来。。。所以我来训贪心了。
P2107 小 Z 的 AK 计划
题目传送门
这种看起来需要用 DP 做的题似乎都需要反悔贪心()
容易发现,一定存在最优解不走回头路,也就是赶路的用时就是选择机房坐标最大值。
也就是说,到某个机房 i,它的赶路用时 xi,实际现在就是要从 1∼i 中选尽可能多的机房,满足 ∑xj≤sum−xi。
这样就可以进行反悔贪心了,维护一个大根堆,从前往后依次考虑前 i 个机房,每次让大根堆对顶尽可能小即可。
