问题1030--最长跳跃路线

1030: 最长跳跃路线

时间限制: 1 Sec  内存限制: 128 MB
提交: 147  解决: 44
[提交] [状态] [讨论版] [命题人:]

题目描述

BSNY来到一个木桩阵,这个木桩阵是由n个木桩组成的,排成直线,每个木桩有个高度hiBSNY可以从某个木桩开始,一直向后跳,但跳跃的位置是由限制的,如果BSNY现在在第i个木桩,想跳到第j个木桩,需要满足条件:

i<j 同时 |hi-hj|>=d

现在BSNY希望能跳的木桩数量最多,问最多可以跳多少木桩?

输入

输入nd

然后第二行输入n个数 h1, h2, … hn

输出

输出多跳多少木桩

样例输入 Copy

5 2
1 3 6 7 4

样例输出 Copy

4

提示

【样例说明】

可以从1点开始,然后跳到第2个点,第3个点,第5个点,总共跳4个点

其他样例:

输入:

10 3

2 1 3 6 9 11 7 3 20 18

输出:

6

 

【数据规模和约定】

1<=n<=10^5  0<=d<=10^9

1<=hi<=10^9

来源/分类

cf474E