交换论证的关键
找到逆序并交换以后，最关键要证明什么？
知识地图
先分清四种规则
它们都用排序，但排序关键字和证明目标完全不同。
交换论证交换后不变差
区间调度结束时间升序
EDF截止时间升序
奶牛W+S 升序
Smithw/p 降序
第一部分 · 自动判分
填空、判断与计算
共 13 题。公式题已经做成选项，重点检查理解，不考键盘输入格式。
普通区间调度
为了选择尽量多的互不冲突区间，每次应优先选择：
区间调度证明
G 是结束最早的区间，最优方案第一个选了 X。为什么能替换？
EDF 字母
在 EDF 中，pi 表示作业 i 的：
EDF 排序规则
为了使最大迟到时间最小，应按什么顺序排列？
EDF 计算
A：pA=3，dA=6；B：pB=2，dB=3。按 A→B，最大迟到时间是多少？
奶牛玩杂技
奶牛从上到下应按照什么顺序排列？
奶牛排序计算
A：W=3，S=5；B：W=6，S=4。谁应放在上面？
Smith 的目标
Smith 规则要最小化哪个量？
Smith 排序规则
作业应该按照什么顺序排列？
Smith 排序计算
| 作业 | p | w |
|---|---|---|
| a | 1 | 2 |
| b | 2 | 5 |
| c | 3 | 7 |
填写最优顺序：
Smith 目标值
上一题最优顺序的 ∑wiCi 等于多少？
Smith 交换证明
CostAB−CostBA 化简后等于：
第二部分 · 进阶简答
先写，再看参考答案
这些题不自动判分，因为证明不应该只匹配固定句子。建议至少写出“对象、交换、比较、结论”四部分。
为什么验证很多样例仍然不能证明贪心正确？
写完后查看参考答案
有限个样例只能说明目前没有发现反例，不能覆盖所有输入。交换论证说明任意最优方案都能在不变差的情况下改造成贪心方案，因此覆盖所有可能输入。
完整证明区间调度为什么选择结束最早的区间。
写完后查看参考答案
设 G 是结束最早的区间，最优方案第一个选择 X。因为 f(G)≤f(X)，用 G 替换 X 后，原来能排在 X 后面的区间仍能排在 G 后面，区间数量不减少。对剩余部分重复，得到一个符合贪心选择的最优方案。
EDF 中，为什么 B 交换到前面以后不会更差？
写完后查看参考答案
若 A→B 是逆序，即 d_A>d_B，交换后 B 少等待 p_A 时间，因此 B 的迟到量不会增加；A 虽然推迟，但它的截止时间更晚。两个作业全部完成的时刻不变，后面作业也不受影响。逐项比较可知交换后的两个迟到量都不超过交换前的最大项。
奶牛题为什么会推导出 W+S，而不是只按重量或力量排序？
写完后查看参考答案
比较相邻奶牛的两种顺序会出现 W_A−S_B 与 W_B−S_A。要求 A 在上不更差，需要 W_A−S_B≤W_B−S_A，移项正好得到 W_A+S_A≤W_B+S_B，因此排序关键字是 W+S。
Smith 证明中，交换相邻 A、B 为什么不会影响后面的作业？
写完后查看参考答案
无论顺序是 A→B 还是 B→A，这一段占用的总时间都是 p_A+p_B，所以这两个作业全部结束的时刻不变，后面每个作业的开始与完成时刻都不变。
写出 Smith 规则的完整相邻交换证明。
写完后查看参考答案
只比较相邻 A、B。化简得 Cost_AB−Cost_BA=w_Bp_A−w_Ap_B。若 w_A/p_A≥w_B/p_B，则 w_Ap_B≥w_Bp_A，所以 Cost_AB≤Cost_BA，A 应在前。若方案存在比率逆序，交换后总代价不增加；不断消除逆序，最终得到 w/p 降序的最优方案。
为什么只证明“相邻两个对象”就能证明整个排序最优？
写完后查看参考答案
任何不符合排序规则的排列都存在相邻逆序。交换一个相邻逆序不会使目标变差，并会减少逆序数量。逆序数量是非负整数，不可能无限下降，所以最终得到没有逆序的贪心顺序；修改过程中始终保持最优，因此整个贪心排序最优。
口头通关
孩子最后应能说出的模板
假设有一个最优方案没有按照贪心规则排列，那么其中存在一对相邻逆序对象。交换它们以后，其他对象不受影响；通过比较交换前后的目标值，可以证明答案不会变差。不断消除逆序，最终得到贪心顺序，所以这个贪心策略是正确的。