贪心：排序推公式#

• 思路

1. 猜一个排序依据（比如按重量、按 deadline、按权值差等）
2. 任取相邻两项 i, j 假设顺序错了，写出交换前/后只与这两头有关的代价/收益表达式
3. 令“交换后更优”得不等式，化简成key(i) < key(j) 或 key(i) > key(j)这个 key 就是 sort 的排序键
4. 全局按 key 排一遍序即可，Greedy 正确性由“相邻交换不影响其余部分”保证

• 经典例题

• 模板代码（奶牛玩杂技）

1
struct Cow { int w, s; };
2
bool cmp(const Cow& a, const Cow& b) {
3
    return (a.w + a.s) < (b.w + b.s);   // 推出来的排序键
4
}
5
sort(cows, cows + n, cmp);

• 注意

1. 能否只比较相邻两项？
2. 交换后其余部分代价是否不变
3. 不等式能否化简成只与单项数据有关的键？
4. 直接sort一遍得到全局最优