充电站选址

题意简述

$n$ 个村庄在直线上的位置为 $a_1,\dots,a_n$。要建 $k$ 个充电站（位置任意），使得每个村庄到最近充电站的距离都不超过 $D$，求最小的整数 $D$。

思路

二分答案

“最小化最大覆盖距离”是典型的二分答案模型：判断“是否存在一种放法使每个村庄到最近站的距离 $\le D$”。

显然答案关于 $D$ 单调：$D$ 越大越容易满足。于是二分 $D \in [0, 10^9]$。

贪心判定

给定 $D$，如何判断 $k$ 个站是否够用？

按村庄位置从小到大考虑。第一个还没被覆盖的村庄位于 $a_{now}$，最优做法是把当前这个站建在 $a_{now} + D$ 处：

• 它到村庄 $a_{now}$ 的距离正好是 $D$，不会浪费；
• 它能覆盖所有位置 $\le a_{now} + 2D$ 的村庄（距离 $\le D$ 即位置 $\in [a_{now}, a_{now} + 2D]$）。

于是每放一个站，就跳过所有位置 $\le a_{now} + 2D$ 的村庄，继续处理下一个未覆盖村庄。统计共需要多少个站，若 $\le k$ 则 $D$ 可行。

复杂度：排序 $O(n\log n)$，二分 $O(\log 10^9)$ 轮，每轮 check 线性扫描 $O(n)$，总复杂度 $O(n \log n + n \log 10^9)$。

正确性

• 贪心：第一个未覆盖的村庄 $a_{now}$ 必须被某个站覆盖，任何方案中覆盖它的那个站位置 $\le a_{now}+D$（否则距离超 $D$）。把站右移放到 $a_{now}+D$ 不会减少覆盖范围，且是“尽量靠右”的最优选择，覆盖的村庄集合是包含关系。因此贪心得到的站数是最少的。
• 二分：满足单调性，标准二分答案。

性质档位提示

• 性质 A（等距）：所有村庄位置等差，站数与间距直接相关，可手算答案。
• 性质 B（$k=n$）：每村一站，答案恒为 $0$，验证二分下界与“$D=0$”的特殊情形。
• 性质 C（$k=1$）：单站覆盖全线段，答案即 $\lceil (\max a - \min a)/2 \rceil$。
• 性质 D（聚簇）：每簇只需一个站，答案取决于簇与簇之间的距离。

实现细节

• 用 long long 存位置与答案（$2D$ 可能达到 $2\times 10^9$）。
• 二分上界取 $10^9$（一个站即可覆盖整条线段的距离上限）。