跳到主要内容

局部约束与构造

本节目标

把环形可行性、双向约束和插入顺序转化为可证明的局部贪心。

本节处理局部选择互相牵制的贪心问题。先识别哪些元素一旦固定就不会再被后续选择破坏，再按影响力排序或分方向传播。

识别信号​

  • 环形资源的总量决定是否存在可行起点。
  • 同一元素同时受到左、右邻居约束。
  • 后续元素只会影响已处理元素的一部分条件，可使用插入构造。

问题模型与核心不变量​

维护“已处理前缀仍可扩展到最优解”的不变量。环形扫描中，负前缀会排除一段起点；双向约束中，两次传播分别给出单向最小需求；插入构造中，已放入元素的计数不再被更弱元素改变。

通用模板​

先确定不可逆或影响范围最大的元素
维护当前前缀的可行性与最小代价
若局部约束失败：批量排除或反向传播
否则固定当前选择并继续构造

模板变体​

母题序列​

  1. 加油站（必学）：用总量与负前缀确定环形起点。
  2. 分发糖果（必学）：将双向相邻约束拆成两次传播。
  3. 根据身高重建队列（拓展）：利用影响力顺序进行位置插入。
  4. 合并果子（拓展）：用小根堆完成最小代价合并。

常见误区​

  • 只验证局部余额，忘记环形问题的总量条件。
  • 右向传播直接覆盖左向结果，破坏已满足的约束。
  • 先放入矮元素，导致后续高元素改变前面计数。
  • 合并果子时选择最大堆，或用过窄整数保存总代价。

迁移方向​

当局部规则同时作用于多个方向时，尝试拆成独立传播；当后续选择只会变弱而不会反向影响时，尝试排序后插入。若约束无法被这种不变量概括，则应考虑动态规划或搜索。