隧道灯

测试数据来自 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

信息

ID
1418
难度
(无)
分类
贪心 点击显示
标签
(无)
递交数
0
已通过
0
通过率
?
上传者