问题 I: 安装监控
传统题
1.000s
时间限制
256MB
内存限制
1 提交
1 解决
【题目描述】
题目描述
有一条街道上有 n
家商店，位置坐标分别为x1,x2,…,xn
。社区计划为这条街道安装摄像机，每一台摄像机有一个最大拍摄距离 d，若它被安装在 x 位置，则它可以拍到位于 [x,x+d]
内的所有商店。
请你帮助社区计算出最少需要多少台摄像机才可以覆盖整个街道上的所有商店。
输入格式
第一行：两个正整数 n 与 d；
第二行：n 个正整数 x1,x2,…,xn
输出格式
单个正整数，表示最少需要的摄像机数量。
数据范围
对于 30% 的数据：1≤n≤100
；
对于 60% 的数据：1≤n≤10000
；
对于 100% 的数据：1≤n≤100000
，1≤d≤100000
，1≤xi≤109
。
给定的数据保证xi
按顺序给出。
样例数据
输入:
6 5
1 4 6 7 9 10
输出:
2
说明:
在位置1建摄像头，覆盖(1,4,6)，然后在位置7建摄像头，覆盖(7,9,10)，故需要两个摄像头