11月-C组(大咖)
Contest is over.
开始 2022-11-05 00:00:00
当前 2025-10-20 02:35:26
结束 2022-11-06 21:00:00

B. 信号塔

题目描述

在一条直线上有 N 个信号塔,编号为 1 \sim N,按照编号从小到大的顺序,均匀分布在该直线上。

由于遇到了极寒天气,有 X 个不同的信号塔出现了故障。

电信公司将紧急维修任务下发到了当地的维修队,要求维修队在最短的时间内维修其中的部分信号塔。维修任务要求在维修后,必须存在连续的 L 个信号塔是可以正常工作的。

时间紧,任务重,人手有限,维修队长找到了维修队中唯一会编程的你,请你编程计算一下,最少要维修多少个信号塔,才能满足维修任务的要求?

输入

1 行读入 3 个整数,NLX,含义如题所述。

接下来 X 行,每行有一个整数,代表了出现故障的信号塔的编号。

输出

输出一个整数,代表为了达到维修任务的要求,最少要维修的信号塔的数量。

样例

输入

10 5 6
2
10
8
6
7
4

输出

2
说明

【样例解释】

维修 1 号到 5 号信号塔中的 2 号、4 号两个信号塔,可以使得 1 号到 5 号,这 5 个连续的信号塔都能正常工作。

【数据范围】

对于 30\% 的数据 1 \le N \le 3000

对于 100\% 的数据,1 \le N \le 10^51 \le X,L \le N

编辑代码
登录

注册
题目参数
时间限制 1 秒
内存限制 512 MB
提交次数 677
通过人数 298
金币数量 2 枚
难度 基础
提交