又称微扰法等
例题
最小化最大延迟惩罚
有 n 个任务，每个任务有一个有用时 \(p_i\) 和一个截止时间 \(d_i\)，若完成时间为 \(c_i\)，要最小化 \(max{c_i - d_i}\)。
考虑如果有两个相邻的 \(i\) 和 \(j\)，不交换答案是：
\[\max(t + p_i - d_i, t + p_i + p_j - d_j)
\]
交换的答案是：
\[\max(t + p_j - d_j, t + p_i + p_j - d_i)
\]
如果交换要不优，那么:
\[\max(t + p_i - d_i, t + p_i + p_j - d_j) \leq \max(t + p_j - d_j, t + p_i + p_j - d_i)
\]
这个我们可以化简为：
\[t + p_i + p_j - d_j \leq t + p_i + p_j - d_i\\
\Leftrightarrow d_i \leq d_j
\]
则说明按照 \(d_i\) 排序使最优的。
最小化最大权值结束时间之积
若加入权值 \(w_i\)，最小化 \(\max{w_ic_i}\)。
这个也是同理，答案是 \(\frac{p_i}{w_i}\)。
习题
最小式
建立表达式树，那么同号的叶子可以随意互换。
我们可以建出来树后跑 dfs，每次在一个极大的同号子树内进行合并，至于合并的方式我们可以猜测是按照运算时间自小至大合并。
简单证一下：
假如我现在只有三个点 \(t_a < t_b < t_c\)，那么考虑 a 和谁合并：
- (a-b)-c
\(ans_1 = \max(O + \max(t_a, t_b), t_c) + O\) - (a-c)-b
\(ans_2 = \max(O + \max(t_a, t_c), t_b) + O\)
\[ans_1 - ans_2 = \max(O + t_b, t_c) - \max(O + t_c, t_b) = \max(O + t_b, t_c) - O - t_c \leq 0
\]
则可知从小到大合并更优。
AT_abc366_f [ABC366F] Maximum Composition
同样考虑邻项交换，我原本的顺序如果是 \(f_a(f_b(x))\)，可以得到交换前后答案之差：
\[A_aB_b - A_bB_a + B_a - B_b = B_a(1 - A_b) - B_b(1 - A_a)
\]
若交换不优，则：
\[B_a(1 - A_b) > B_b(1 - A_a)\\
\Leftrightarrow \frac{B_a}{1 - A_a} > \frac{B_b}{1 - A_b}
\]