题解【luoguP3644 [APIO2015]八邻旁之桥】

时间:2023-03-08 15:59:31

题目链接


题解

家和公司在同侧

  • 简单,直接预处理掉

若 \(k=1\)

  • 取所有的居民的\(\frac{家坐标+公司坐标}{2}\)的所有坐标的正中间建一座桥,使所有居民到的距离最小。

  • 实现方法:线段树(用来求中位数)

期望得分:\(14 + 8 = 22\)(如果按子问题给分)


若 \(k=2\)

  • 取每个线段的中点,如果靠近左边的桥,就往左边过桥,否则往右边过桥。

  • 这样的话,先把线段按\(l+r\)排序,如果枚举一个分割线,左右两边分别转换成为\(k=1\)的情况了

  • 实现方法:线段树(用来求中位数)

期望得分:100