题源:青岛 58 中高一作业。新定义能这么出?
直接考虑(3),这是一个经典问题 [NOIP 2012 提高组] 国王游戏 的模型,即临项交换法贪心。
题意即重排一个给定的二元组序列,使得 \(\max_{i=1}^n f_i\) 最小,其中, \(f_i = \sum_{k=1}^{i-1}(h_k-s_i)\)。
考虑重排序列的过程本质上是在进行若干次相邻两项的交换,即类似冒泡排序的过程。
不妨令 \(j = i + 1\),记 \(sum_i = \sum_{k=1}^i h_k\),则交换前:
\[\begin{aligned}
f_i &= sum_{i-1}-s_i \\
f_j &= sum_i-s_j=sum_{i-1}+h_i-s_j
\end{aligned}
\]
交换 \(i, j\),记现在 \(i,j\) 位置上的 \(f\) 值为 \(f_i',f_j'\),则:
\[\begin{aligned}
f_i' &= sum_{i-1} - s_j\\
f_j' &= sum_{i - 1} + h_j - s_i
\end{aligned}
\]
答案只与最大的一项有关,所以我们要让较大的项尽可能小。所以当且仅当 \(sum_{i-1}+h_j-s_i<sum_{i-1}+h_i-s_j\) 时,交换是更优的。
整理,即:\(h_j+s_j<h_i+s_i\) 时,交换是更优的。
所以,我们按照 \(h_i+s_i\) 从小到大排序即可,特别注意的是,在此题中的不等号具有传递性,这是我们从邻项推广到整个序列的前提,不满足的典型例题是 皇后游戏,复习到的时候会写一下。