AC. 梦想

frank_c1

[APIO 2015] Palembang Bridges

发布于2017年04月16日 | 暂无评论 | 390阅读 | 线段树,贪心

题意简述

城市中有一条河,河两岸A,B分别有10 ^ 9 + 1个建筑。

我们沿某方向把两岸的建筑分别编号为010 ^ 9。相邻建筑距离为1,两岸编号相同的建筑相对,距离为1

现在有n条路径,第i条路径从P_i岸建筑S_iQ_i岸建筑T_i

由于需要过河,我们需要在河流上建桥。具体地,你每次可以选择一对相对的建筑,在之间建一座桥。至多建K座桥。

设建完桥后,第i条路径的最短长度是D_i。你需要最小化所有D_i之和。

1 \le n \le 10 ^ 5, 1 \le K \le 2, 0 \le S_i, T_i \le 10 ^ 9

算法讨论

首先所有同岸的路径最短长度确定,计入答案后可以全部扔掉。其余所有路径都需要过桥,这一部分贡献也可先统计。

考虑K = 1。设选在x位置建桥,那么一条路径对答案的贡献就是|S_i - x| + |T_i - x|。由于S_iT_i贡献独立,就相当于最小化所有S_i, T_i和某个点距离的总和。这是一个经典问题,x取所有S_iT_i的中位数时必定最优。

再来考虑K = 2。设我们选了两个位置L, R建桥,那么我们思考哪些路径会走L桥,哪些走R桥呢?不妨先考虑所有满足L \le S_i, T_i \le R的路径。若路径iL桥是较优的,则有

S_i + T_i - 2L \le 2R - S_i - T_i \Rightarrow S_i + T_i \le L + R \Rightarrow \frac{S_i + T_i}{2} \le \frac{L+R}{2}

即路径中点不超过L, R中点的路径走L较优。进一步地,容易将这个结论推广到所有S_i, T_i

但是如果枚举L, R就超时啦。观察上述结论,可以发现这个结论还有一层含义,即最优解中存在一个分界点x,满足所有路径中点不超过x的路径走左边桥较优,其余的走右边桥较优。

于是算法的框架就清晰了。先把路径按中点排序。枚举i,计算前i条路径走左边桥,其余走右边桥的答案。我们发现需要快速地对两边分别算出中位数。离散化后在权值线段树上二分即可。时间复杂度O(n \log n)