题目链接 https://leetcode.com/problems/apply-operations-to-maximize-frequency-score/description/
题目描述
在一个一维坐标轴上有 N 个村庄 (0-indexed)，坐标 A[i] 为正整数。 给定最大交通成本 k.
我们准备设立一个邮局。选择一个区间 [L,R] 和邮局坐标 x, 定义交通成本 $c=\sum_{i=L}^{R}|x-A_i|$ 。 在满足 $c<=k$ 的前提下，找到最大的区间。
题目分析
我们先考虑一个子问题：对于给定的区间 [L,R]，我们如何求出最低的交通成本。对此，我们先引入三个引理：
- $A_L <= x_{opt} <= A_R$ (Too Trivial)
- 最优的邮局坐标一定和某个村庄(M-th)重合，即 $x_{opt}=A_M$.
- 如果区间长度为奇数，则 $M_{opt}$ 就是最中心的一个村庄。如果为偶数，那最中间的两个村庄都是最优的选择.
在此基础上，我们可以通过如下变换，利用前缀和，在常数时间内求出特定区间的交通成本 $c$
\[\begin{aligned} c &= c_L + c_R \\ c_L &= \sum_{i=L}^{M} A_M - A_i \\ &= (M-L+1)A_M - \sum_{i=L}^{M}A_i \\ &= (M-L+1)A_M - ( \sum_{i=0}^{M}A_i - \sum_{i=0}^{L-1} A_i)\\ c_R &= \sum_{i=M}^{R} A_i - A_M \\ &= \sum_{i=0}^{R} A_i - \sum_{i=0}^{M-1}A_i - (R-M+1)A_M \end{aligned}\]算法实现
有了如上的分析，实现 Sliding Window 算法就非常容易了。将所有坐标排序后，先求出前缀和 $P_V = \sum_{i=0}^{V} A_i$
我们将初始的 Window 设置为 $L=R=0$. 显然，此时 $c=0$,是一种合法的情况。按照通常的 Sliding Window 的做法，我们不断移动右边界 $R$，在 $c>k$ 时移动左边界 $L$. 我们的贪心算法会找出最优解。
引理证明
Lemma 2
使用反证法，假设 $A_M < x^* < A_{M+1} $, 此时交通成本
\(\begin{aligned}
c &= c_L + c_R \\
&= \sum_{i=L}^{M}( x^* - A_i )+ \sum_{i=M+1}^{R} (A_i - x^*)\\
\end{aligned}\)
我们将邮局向左移动至 $A_M = x’ < x^* < A_{M+1} $, $x^*-x’=d>0$
左侧的 (M-L+1) 个村庄的成本会下降 (M-L+1)d, 而右侧的 (R-M) 个村庄的成本会上升 (R-M)d.
这样，我们分三种情况讨论：
- 如果 $x^*$ 左侧的村庄更多，即 $M-L+1 > R-M$, 则 $x’＝A_M$ 优于 $x^*$
- 如果两侧的村庄一样多，移动至 $x’＝A_M$ 不会得到更差的结果
- 如果右侧的村庄更多，易证 $x’'＝A_{M+1}$ 优于 $x^*$
Lemma 2 得证。
Lemma 3
可以沿用类似 Lemma 2 的计算方法。区间长为奇数时，根据引理，M = (R-L) / 2 + L。 如果我们要向左移动到 $A_{M-1}$, $A_M - A_{M-1}=d>0$。 左侧的村庄 [L, M-1] 的成本会下降，右侧 [M+1, R] 的成本会上升。这两部分抵消后，村庄 M 的交通成本会增加 d，得到一个更差的结果。
如果区间长为偶数，用同样的方法可以得到，在最中间的两个村庄之间移动邮局的 $\Delta=0$.
后记
这道题几个月前被丢到了我的 list上。我最开始没有意识到 Lemma 3, 而是试图维护一个三元数组 (L, M, R)，在Sliding的过程中动态调整邮局的位置。顺着这个思路想下去，就是越想越偏离正解。 看了答案以后，意识到最优的邮局地点是固定的，也学到了借助前缀和来求特定区间的交通成本，从而避免了手动维护当前Window的成本。
在写题解的过程中，发现 Lemmy 2&3 的证明过程其实可以合并。我之前做这类题目时，对证明过程理解不到位。写这篇题解让我的认识深入了很多，也发现完全可以用很简明的方式证明。
LeetCode 原题里没有提到坐标，我借用 IOI2000 邮局 的题目背景，感觉直观了不少。