#P12648. [KOI 2024 Round 2] 路灯
[KOI 2024 Round 2] 路灯
题目背景
试题来源:https://koi.or.kr/archives/。中文翻译做了少量本土化修改。
按照署名—非商业性使用—相同方式共享 4.0 协议国际版进行授权。
题目描述
在一条数轴表示的直线道路上,安装了 盏路灯。每盏路灯的位置按从左到右依次为 。
我们定义某个位置 的“黑暗程度”为该位置到所有路灯之间距离的最小值。即,黑暗程度等于数列 中的最小值。其中, 表示 的绝对值,若 ,则 ;若 ,则 。
例如,若 ,且路灯分别位于 、、,那么从位置 到 的黑暗程度如下:
位置 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
---|---|---|---|---|---|---|---|---|---|---|---|
黑暗程度 | 1 | 0 | 1 | 0 | 1 | 2 | 1 | 0 | 1 | 2 | |
是否有灯 | O | O | O |
给定一个整数 ,我们关心从 到 这 个整数位置的黑暗程度。请你编程,输出其中按黑暗程度从小到大排序后的前 小的值。
输入格式
第一行输入三个整数 ,用空格隔开。
第二行输入 个整数 ,表示每盏路灯的位置,以空格隔开。
输出格式
输出 行,第 行输出从小到大排序后的第 小黑暗程度值。
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
提示
约束条件
- 所有输入为整数。
子问题
- (10 分)
- (20 分)
- (15 分) 且 整除 ,且
- (20 分)
- (35 分)无额外限制条件
翻译由 ChatGPT-4o 完成