贪心选择与证明
本节目标
从交换论证出发，判断一个局部选择能否安全地通向全局最优。
贪心不是“每次看起来最划算就选什么”。它必须先确定一个局部选择，再证明任意最优解都能被替换成同样的选择而不变差。这个替换过程就是交换论证；若替换后答案不变差，当前选择便是安全的。
识别信号
- 所有候选项都可排序，且题目要求最小总等待、最小最大风险或最多匹配数量。
- 调整两个相邻候选项的先后顺序，会直接影响目标函数。
- 一旦先处理的候选固定，剩余部分仍是同类子问题。
问题模型与核心不变量
先写清候选选择、排序规则和交换对象。若最优排列中出现一个“逆序对”，交换这两个相邻项不会使目标更差，便可持续交换到满足排序规则的最优排列。处理前缀时的不变量是：已确定的前缀存在一个同样好的最优解与它一致。
通用模板
按可证明的关键字排序
维护已完成前缀的必要状态
依次尝试当前候选：
若它满足当前最小需求或能改善目标：接受它
否则丢弃或留给后续候选
排序本身不是证明；排序键必须来自交换两个相邻元素后的差值。
模板变体
- 资源匹配中，用最小可行资源满足最小需求，避免大资源被小需求浪费。
- 总等待时间中，交换两个服务时长为
a、b的顾客，较短者在前不会增加等待和。 - 最大风险中，比较两头牛的顺序后可得到
w + s的排序键；风险定义必须先固定为“上方总重量减当前强壮值”。
母题序列
常见误区
- 只说“排序后显然最优”，却没有比较交换前后的目标。
- 将“当前最优”误当成“局部数值最大”；正确选择可能是最小可行资源。
- 没有固定风险或代价的定义，导致排序规则和样例计算不一致。
- 忽略中间和可能超出
int的题目范围。
迁移方向
交换论证是区间按端点排序、最小代价合并和队列重建的共同基础。若无法构造安全交换，或选择会影响多个未来状态，则要警惕问题可能需要动态规划或搜索。