基于临项交换证明的排序贪心

hcx2012 · 2026-08-19 08:07:31 · 算法·理论

部分序列贪心题目的答案是「将序列按某一关键字排序」，而这类问题通常需要使用交换法证明贪心。

通法

先考虑两个相邻元素（不交换、交换后比较），再归纳法证明；需要注意的是：交换两个相邻元素对答案的影响，只能与这两个元素本身有关，而与序列中其他元素的位置无关，才可以如此贪心。

文章可能会少考虑一些不等号取等的边界情况。

考虑 j=i+1 时的顺序，若当前顺序（不交换）更优，则有：（式子去除了在这里考虑时的不变量，下同，如非特殊说明不变量都不会影响不等式的符号情况）

\max(\frac{1}{b_i},\frac{a_i}{b_j})<\max(\frac{1}{b_j},\frac{a_j}{b_i})

由 a_i,a_j\ge 1，\frac{1}{b_i}\le\frac{a_j}{b_i} 且 \frac{1}{b_j}\le\frac{a_i}{b_j}。

得到 \frac{1}{b_i}\le RHS，原式化为：\frac{a_i}{b_j}<\max(\frac{1}{b_j},\frac{a_j}{b_i})。

同理，可以得到 \frac{a_i}{b_j}\le\frac{a_j}{b_i}。

交叉相乘，a_ib_i\le a_jb_j。

按照 a_ib_i 作为关键字升序排序即可。

令 P_i=\frac{A_i}{B_i}，E_i 为「成功点亮第 i 盏灯」的期望时间。

数学推导不在本文所述范围内，这里直接给出 E_i 的式子：

E_i=\frac{T_i+E_{i-1}}{P_i}=\frac{T_1+T_2P_1+T_3P_1P_2+\cdots}{P_1P_2P_3\cdots P_i}

不难发现，分母对答案无影响，我们这里只考虑分子。

我们令 j=i+1，考虑顺序，i 在 j 前面更优当且仅当：

T_i+T_jP_i<T_j+T_iP_j

移项整理，\frac{T_i}{1-P_i}<\frac{T_j}{1-P_j}，所以按 \frac{T_i}{1-P_i} 升序排序即可。

题目是：给定两个长为 n 序列 c,d，均可随意调整顺序，求 \sum^n_{i=1}|c_i-d_i| 的最小值。

首先令 f(x)=|x-a|-|x-b|，其中 a,b 为常数且 a<b。

分类讨论：

边界情况：

因此，我们证明了 f 在适当值域内是单调不降的。

可以发现 a=b 的情况也可以按照上文所述方式证明得出。

所以，当 c_i\le c_{i+1} 时 f(c_i)\le f(c_{i+1})；即对所有 a\le b，都有 |c_i-a|-|c_i-b|\le |c_{i+1}-a|-|c_{i+1}-b|，移项，得 |c_i-a|+|c_{i+1}-b|\le |c_{i+1}-a|+|c_i-b|。

我们令 d_i=a，d_{i+1}=b，显然我们需要先令序列 d 按升序排列，才能套用刚才求出的不等式。

仅考虑 i,i+1 这两个位置，若 c_i>c_{i+1}，则交换 c_i 和 c_{i+1} 一定不劣。

如此归纳我们就证得了，当 d 是升序排列的情况下，c 也按升序排列，一定能够得到最优答案。

稍加思考便可得出，对于顺序不定的 c,d，一定有 c 和 d 均按升序排列，能得出最优的答案。