P12648 [KOI 2024 Round 2] 路灯

试题来源：。中文翻译做了少量本土化修改。 按照[署名—非商业性使用—相同方式共享 4.0 协议国际版](https://creativecommons.org/licenses/by-nc-sa/4.0/deed.zh-hans)进行授权。

在一条数轴表示的直线道路上，安装了 $N$ 盏路灯。每盏路灯的位置按从左到右依次为 $A_1 < A_2 < \cdots < A_N$。 我们定义某个位置 $x$ 的“黑暗程度”为该位置到所有路灯之间距离的最小值。即，黑暗程度等于数列 $|A_1 - x|, |A_2 - x|, \dots, |A_N - x|$ 中的最小值。其中，$|y|$ 表示 $y$ 的绝对值，若 $y \geq 0$，则 $|y| = y$；若 $y < 0$，则 $|y| = -y$。 例如，若 $N = 3$，且路灯分别位于 $A_1 = 1$、$A_2 = 4$、$A_3 = 8$，那么从位置 $x = 0$ 到 $x = 10$ 的黑暗程度如下： | 位置 $x$ | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | |----------|---|---|---|---|---|---|---|---|---|----|----| | 黑暗程度 | 1 | 0 | 1 | 1 | 0 | 1 | 2 | 1 | 0 | 1 | 2 | | 是否有灯 | | O | | | O | | | | O | | | 给定一个整数 $L$，我们关心从 $x = 0$ 到 $x = L$ 这 $L+1$ 个整数位置的黑暗程度。请你编程，输出其中按黑暗程度从小到大排序后的前 $K$ 小的值。

第一行输入三个整数 $L,\ N,\ K$，用空格隔开。 第二行输入 $N$ 个整数 $A_1, A_2, \dots, A_N$，表示每盏路灯的位置，以空格隔开。

输出 $K$ 行，第 $i$ 行输出从小到大排序后的第 $i$ 小黑暗程度值。

**约束条件** - 所有输入为整数。 - $1 \leq L \leq 10^{18}$ - $1 \leq N \leq 3 \times 10^5$ - $1 \leq K \leq 5 \times 10^5$ - $K \leq L + 1$ - $0 \leq A_1 < A_2 < \cdots < A_N \leq L$ **子问题** 1. （10 分）$N = 1$ 2. （20 分）$N \leq 2\,500,\ L \leq 2\,500$ 3. （15 分）$2 \leq N$ 且 $N - 1$ 整除 $L$，且 $A_i = \dfrac{L}{N-1} \times (i - 1)$ 4. （20 分）$L \leq 5 \times 10^6$ 5. （35 分）无额外限制条件 翻译由 ChatGPT-4o 完成