问题2419--关灯

2419: 关灯

[命题人 : ]
时间限制 : 1 sec  内存限制 : 128 MB

提交

题目描述

已知有n盏灯,每盏灯的位置ai均不相等,当两盏灯之间的距离小于k时,如果在这个距离之间有灯亮着,那么就可以关掉在这个距离内的所有亮着的灯(即如第i-1盏灯与第i+1盏灯的距离≤k,那么可以关掉第i盏灯)。
求能关掉的灯的最大数量。
第一盏灯和最后一盏灯必须亮着(位置ai最大和最小的两盏灯)。

输入

第一行两个数,n和k。
1≤n≤100
k<1000
第二行n个数,即每盏灯的位置。

输出

一个数,即一段区域内能关闭的灯的最大值。

样例输入 Copy

3 3
1 2 3

样例输出 Copy

1

提示