题目背景

试题来源：https://koi.or.kr/archives/。中文翻译做了少量本土化修改。

按照署名—非商业性使用—相同方式共享 4.0 协议国际版进行授权。

题目描述

在一条数轴表示的直线道路上，安装了 $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		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$ 小黑暗程度值。

10 3 4
1 4 8

0
0
0
1

4 5 5
0 1 2 3 4

0
0
0
0
0

7 1 4
3

0
1
1
2

9 4 10
0 3 6 9

0
0
0
0
1
1
1
1
1
1

提示

约束条件

• 所有输入为整数。
• $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 完成