#Y1001. 安装监控

安装监控

题目描述

有一条街道上有 n 家商店,位置坐标分别为x1,x2.....xnx_1,x_2.....x_n。社区计划为这条街道安装摄像机,每一台摄像机有一个最大拍摄距离d,若它被安装在 x 位置,则它可以拍到位于 [x,x+d]内的所有商店。

请你帮助社区计算出最少需要多少台摄像机才可以覆盖整个街道上的所有商店。

输入格式

​第一行:两个正整数n与d; 第二行:n 个正整数 x1,x2......xnx_1,x_2......x_n

输出格式

单个正整数,表示最少需要的摄像机数量。

输入样例

6 5
1 4 6 7 9 10

输出样例

2

样例说明

在位置1建摄像头,覆盖(1,4,6),然后在位置7建摄像头,覆盖(7,9,10),故需要两个摄像头

数据范围

  • 对于 30% 的数据: 1n100
  • 对于 60% 的数据: 1n10000
  • 对于 100% 的数据:1n100000,1d100000,1xi10^9
  • 给定的数据保证xi按顺序给出。