贪心综合

◎

本节目标

将趋势压缩、数字回退和调度骨架迁移到不显眼的综合贪心问题。

本节把前面学到的“保留支配状态”“遇到冲突向高位回退”和“由最紧约束构造下界”组合起来，处理不属于单一模板的综合题。

识别信号

• 同方向的中间状态不会改善后续选择。
• 为满足上界，必须在最右冲突处牺牲一个更高位。
• 少数最高频对象决定了空位或时间下界。

问题模型与核心不变量

扫描过程中只保留对后缀最有利的端点或骨架。趋势题维护上升、下降两种最优长度；数字题维护已确认前缀合法并记录回退位置；调度题维护最高频任务形成的不可压缩骨架。

通用模板

识别当前状态对未来的支配关系
发现方向冲突时，只回退最小必要的高位或状态
用允许的最大值填充不再受约束的后缀或空位
把结构下界与元素总量下界取最大

模板变体

• 摆动序列：只保留趋势转折点。
• 单调递增的数字：冲突高位减一，后缀置九。
• 任务调度器：最高频任务建立冷却间隔骨架。

母题序列

1. 摆动序列（必学）：压缩同向变化，保留趋势转折。
2. 单调递增的数字（拓展）：从右向左处理连锁回退。
3. 任务调度器（拓展）：用最高频任务与总数修正调度下界。

常见误区

• 把相等差值当成趋势变化。
• 数字只回退一次，遗漏更高位的新冲突。
• 任务调度只返回骨架，忽略其他任务能填满空位。
• 将没有安全交换或支配关系的问题强行套用贪心。

迁移方向

面对综合题，先写出“哪些状态可以被删除、哪些冲突必须回退、哪个对象构成下界”，再判断局部选择能否由交换、不变量或等价变换证明。