P3644 [APIO2015] 巴邻旁之桥 题解

注意到 $k\in\lbrace 1,2\rbrace$（现在你已经做完了这个题最难的地方），因此猜测是直接分两类讨论。

$k=1$

可以把问题转化为：找到最小的 $x$ 使得 $\sum\limits_{i=1}^n|a_i-x|+\sum\limits_{i=1}^n|b_i-x|$ 的值最小。这是经典的贪心模型，直接把 $a_i,b_i$ 合并到一个数组 $c$ 中然后升序排序，取 $x=c_n$ 即为最优解。证明直接调整法即可。

$k=2$

类比 $k=1$ 的做法，必然是建两座桥然后左半部分的走坐标的桥，右半部分的走右边的桥，因此容易想到枚举中间的分界点 $p$ 然后对两侧分别做 $k=1$ 的处理，可以简单维护有序数组做到 $O(n^2)$ 求解问题。

考虑优化时间复杂度。考虑记 $F(p)$ 为分界点为 $p$ 时的答案，但是 $F(p)$ 看上去没有单调单峰等性质。一个想法是直接对 $F(p)$ 跑模拟退火（我不知道这个能不能过）。注意到其实不需要真的维护两个有序数组，只需要得知两个数组的中位数值即可，因此考虑从左到右扫描所有本质不同的位置 $p$ 然后对两个集合做单点插入 / 单点删除操作，并分别维护两个集合的中位数以及 $\sum\limits_{i=1}^n|a_i-x|$ 的值（已知元素数量和数组中位数值后这个是容易维护的）。用对顶堆来维护即可做到 $O(n\log n)$ 通过该题。