[BZOJ4071/Luogu3644][Apio2015]巴邻旁之桥 (线段树,数论,离散化)

发布于 2018-02-17  143 次阅读


本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ4071/Luogu3644][Apio2015]巴邻旁之桥 (线段树,数论,离散化)

Description

一条东西走向的穆西河将巴邻旁市一分为二,分割成了区域 A 和区域 B。
每一块区域沿着河岸都建了恰好 1000000001 栋的建筑,每条岸边的建筑都从 0 编号到 1000000000。相邻的每对建筑相隔 1 个单位距离,河的宽度也是 1 个单位长度。区域 A 中的 i 号建筑物恰好与区域 B 中的 i 号建筑物隔河相对。
城市中有 N 个居民。第 i 个居民的房子在区域 Pi 的 Si 号建筑上,同时他的办公室坐落在 Qi 区域的 Ti 号建筑上。一个居民的房子和办公室可能分布在河的两岸,这样他就必须要搭乘船只才能从家中去往办公室,这种情况让很多人都觉得不方便。为了使居民们可以开车去工作,政府决定建造不超过 K 座横跨河流的大桥。
由于技术上的原因,每一座桥必须刚好连接河的两岸,桥梁必须严格垂直于河流,并且桥与桥之间不能相交。当政府建造最多 K 座桥之后,设 Di 表示第 i 个居民此时开车从家里到办公室的最短距离。请帮助政府建造桥梁,使得 D1+D2+⋯+DN 最小。

Http

BZOJ
Luogu

Tag

线段树,数论,离散化

解决思路

看到\(K\)的数据范围,要根据\(K==1\)和\(K==2\)分别讨论。
先把只在一边的单独算掉,排除在外。
首先\(K==1\)的情况,只有一座桥,那么就是所有人都要经过这个桥,假设这个桥的位置是pos,那么式子就是\(\sum (|A[i]-pos|+|B[i]-pos|)\),直接把\(A[i]\)和\(B[i]\)放在一起排序求出中位数即可。
然后是\(K==2\)的情况。有了前面的例子,我们可以知道,一个人一定是走离自己两边位置的中位数更近的那一座桥,那么可以把人按照中位数排序,枚举分割成两部分,两部分分别按照\(K==1\)的方式来算。
那么接下来的问题就是动态求中位数,这里用权值线段树的方式来求,具体来说就是找到中间的\(rank\),分割查看左边的大小与当前要查询的\(rank\)作比较,如果左边大于\(rank\)则走左边,否则走右边,类似于平衡树中求第\(K\)大。

代码

本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ4071/Luogu3644][Apio2015]巴邻旁之桥 (线段树,数论,离散化)


HNCJ OIer