【ARC215A】Zombie

AT_arc215_a [ARC215A] Zombie - 洛谷

给出 $n$ 个僵尸的位置，在一个长为 $L$ 的数轴上，你需要放 $k$ 块脑子，每个僵尸每秒都会向脑子方向移动 $1$，问脑子存在的最长时间和。

$1 \le n \le 2 \times 10 ^ 5, 1 \le k \le 10 ^ 9, 1 \le a_i \le 10 ^ 9, 1\le L \le 10 ^ 9$。

其中，所有僵尸的位置均为偶数。

我们考虑贪心的策略，其中，对于贪心策略来讲，无非就是选择中间或者两边。

我们将中间的区间按大小排序，枚举选多少个区间，直接预处理前缀和，或者枚举的时候累计，最后 $\mathcal{O}(1)$ 计算剩余的脑子放在两边的方案数。

时间复杂度 $\mathcal{O}(n \log n)$。