隧道灯

测试数据来自 system/1755

作业已超过截止时间,您无法递交本题目。

时间限制:1秒  内存限制:256M


【题目描述】

  高速路上一般都有很多隧道,为行车安全,隧道中灯要一直亮着。

  但是为了节约,一般隧道中的灯都没有必要全部点亮,在保证照明的情况下,需要关掉尽量多的灯。具体来说,设隧道中有 \(n\) 盏灯以及每盏灯的位置 \(p_i\)(距离隧道一侧入口的距离),\(p_i\) 均不相等,当某两盏灯的距离小于 \(D\) 时,那么在这两盏灯之间的灯就可以关掉(即若第 \(i-1\) 盏与第 \(i+1\) 盏的距离小于等于 \(D\),则可以关掉第 \(i\) 盏)。

  现在给出一个隧道中灯的为止信息和照明参数 \(D\),求在保证洞里的光线是充足的情况下,最多可以关掉多少盏灯?

  注意:距离一侧入口最近和最远的两盏灯必须是亮着。

【输入格式】

  第一行两个数,\(N\) 和 \(D\),表示有隧道中有 \(N\) 盏灯,照明距离参数为 \(D\)。
  接下来的 \(N\) 行,每行一个整数 \(p_i\),表示每盏灯的位置。

【输出格式】

  一个数,能关掉灯的最大数目。

【输入输出样例】

 Input

3 3
1
2
3

 Output

1

【数据限制】

  对于 \(100\%\) 的数据,\(1<N<100000\),\(1 ≤ D,p_i ≤ 10^9\)。

【来源】

  Mr.he

寒假作业(二)

未认领
状态
已结束
题目
10
开始时间
2024-01-20 00:00
截止时间
2024-02-20 23:59
可延期
24.0 小时