第一关 · 掌握套路
证明不是“我觉得对”
我们要把任意一个最优方案改成贪心方案，并保证每次修改都不会让答案变差。
假设最优方案
先承认有一个最好的完整方案，记作 O。
找到第一个不同
找出 O 和贪心规则不一样的位置，通常是一对相邻逆序。
交换或替换
把它改成贪心要求的样子，只动最小的一部分。
证明不会变差
仍然合法，答案不减少或目标值不增大，然后继续交换。
万能句：假设最优方案没有按贪心规则排列。找到一对排反的相邻对象，交换它们，并证明交换后答案不会更差。不断交换，最终得到贪心顺序，因此贪心策略正确。
实验一 · 区间调度
结束得早，给后面让位置
目标：选择尽量多的互不冲突区间。贪心规则：每次选择结束时间最早的区间。
把最优方案的第一个区间替换掉
012345678
原最优方案：X、H、I，共 3 个区间。
为什么替换后仍然最优？
- G 是结束最早的区间，所以 f(G) ≤ f(X)。
- 原来能放在 X 后面的区间，也一定能放在 G 后面。
- 替换后仍然选择 3 个区间，数量没有减少。
- 因此，至少存在一个以 G 开头的最优方案。
口头回答要说“替换最优方案以后仍然合法、数量不减少”，不能只说“结束早看起来更好”。
实验二 · 最大迟到时间
截止时间早的，先做
EDF 规则：按照截止时间从早到晚安排。点击交换一对相邻逆序作业。
当前顺序
A用时 3
截止 6
截止 6
B用时 2
截止 3
截止 3
最大迟到时间0
逆序数量1
A 的截止时间 6 比 B 的 3 晚，却排在 B 前面：这是逆序。
第一步：先把字母翻成人话
p：需要多久processing time，处理时间。例如 pA 就是做 A 需要的时间。
d：最晚何时deadline，截止时间。例如 dB 就是 B 的截止时间。
C：何时做完completion time，完成时刻。例如 CA 就是 A 实际做完的时刻。
t：已经过去多久开始做 A、B 以前，前面的作业已经用掉的时间。
右下角的小字母叫“下标”：pA 读作“p A”，表示 A 的处理时间。
第二步：先用本页数字算一遍
A 需要 3，截止 6；B 需要 2，截止 3。因为 6 > 3，A→B 是逆序。
交换前：A → B
A：3 时完成，迟到 max(3−6,0)=0
B：5 时完成，迟到 max(5−3,0)=2
最大迟到：2
交换后：B → A
B：2 时完成，迟到 max(2−3,0)=0
A：5 时完成，迟到 max(5−6,0)=0
最大迟到：0
第三步：把数字换回字母
设一对逆序作业为 A→B，开始前已经用时 t，且 dA > dB。
交换前的上界A 的迟到量不超过 B：
t+pA−dA ≤ t+pA+pB−dB
t+pA−dA ≤ t+pA+pB−dB
交换后的 Bt+pB−dB ≤ t+pA+pB−dB
交换后的 At+pA+pB−dA < t+pA+pB−dB
结论交换后两项都不超过交换前的最大项；再分别和 0 取最大值，大小关系仍不改变。所以最大迟到时间不会增加。
只要还有逆序，就继续交换。每次交换都减少一个逆序，最后一定变成截止时间升序，也就是 EDF。
实验三 · 奶牛玩杂技
亲手调参数，观察压扁指数
规则：从上到下按 W + S 升序排列。拖动滑块，再交换两头奶牛看看。
它们上方还有固定重量 T = 4
当前顺序
交换顺序
🐄
奶牛 A
🐮
奶牛 B
🌱 地面
当前最大压扁指数：
压扁指数为负数，表示奶牛的力量足够，目前还扛得住。
① 假设 A 应在 B 上面WA+SA ≤ WB+SB
② 移项WA−SB ≤ WB−SA
③ 另一项也不大因为 WB ≥ 0，所以 −SA ≤ WB−SA。
④ 比较最大值max(−SA, WA−SB) ≤ max(−SB, WB−SA)
两边再加相同的 T，不等号不变，所以 A 在上不会更差。
两边再加相同的 T，不等号不变，所以 A 在上不会更差。
最后一关 · 三题通关
会操作，还要会证明
每类题各答一道。答错没关系，反馈会告诉你缺少哪一步。
已答对 0 / 3