#P12648. [KOI 2024 Round 2] 路灯

    ID: 14200 远端评测题 2000ms 1024MiB 尝试: 0 已通过: 0 难度: 3 上传者: 标签>模拟数学2024枚举排序KOI(韩国)

[KOI 2024 Round 2] 路灯

题目背景

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

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

题目描述

在一条数轴表示的直线道路上,安装了 NN 盏路灯。每盏路灯的位置按从左到右依次为 A1<A2<<ANA_1 < A_2 < \cdots < A_N

我们定义某个位置 xx 的“黑暗程度”为该位置到所有路灯之间距离的最小值。即,黑暗程度等于数列 A1x,A2x,,ANx|A_1 - x|, |A_2 - x|, \dots, |A_N - x| 中的最小值。其中,y|y| 表示 yy 的绝对值,若 y0y \geq 0,则 y=y|y| = y;若 y<0y < 0,则 y=y|y| = -y

例如,若 N=3N = 3,且路灯分别位于 A1=1A_1 = 1A2=4A_2 = 4A3=8A_3 = 8,那么从位置 x=0x = 0x=10x = 10 的黑暗程度如下:

位置 xx 0 1 2 3 4 5 6 7 8 9 10
黑暗程度 1 0 1 0 1 2 1 0 1 2
是否有灯 O O O

给定一个整数 LL,我们关心从 x=0x = 0x=Lx = LL+1L+1 个整数位置的黑暗程度。请你编程,输出其中按黑暗程度从小到大排序后的前 KK 小的值。

输入格式

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

输出格式

输出 KK 行,第 ii 行输出从小到大排序后的第 ii 小黑暗程度值。

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

提示

约束条件

  • 所有输入为整数。
  • 1L10181 \leq L \leq 10^{18}
  • 1N3000001 \leq N \leq 300\,000
  • 1K5000001 \leq K \leq 500\,000
  • KL+1K \leq L + 1
  • 0A1<A2<<ANL0 \leq A_1 < A_2 < \cdots < A_N \leq L

子问题

  1. (10 分)N=1N = 1
  2. (20 分)N2500, L2500N \leq 2\,500,\ L \leq 2\,500
  3. (15 分)2N2 \leq NN1N - 1 整除 LL,且 Ai=LN1×(i1)A_i = \dfrac{L}{N-1} \times (i - 1)
  4. (20 分)L5000000L \leq 5\,000\,000
  5. (35 分)无额外限制条件

翻译由 ChatGPT-4o 完成