2434 - 安保设置

题目描述

华罗庚大道在国庆时准备举办庆祝活动,为了确保活动的顺利举行,A市的相关部门要在该条道路上设置安保人员。

该大道可以看作一条坐标从 010000 的线段,该线段上有 n 个点可以设置安保人员,每个点的安保人员负责安保的范围是为区域半径为 r 的区间,也就是说,位于坐标值为 x 的位置的安保人员,将会负责 [x-r,x+r] 的区域。

请问,这 n 个点至少要选择几个点设置安保人员,才能使得整条大道的所有位置都有安保人员负责?

输入

第一行两个整数 nrn≤1000r≤20000)。分别表示可设置安保人员的位置数量和安保人员可以负责的区域半径。

第二行 n 个数,分别表示可设置安保人员的点的坐标。

输出

一个数,表示最少需要选择设置安保人员的位置数量。(本题测试数据确保有解)

样例

输入

5 4000
0 1000 3000 2000 9000

输出

2
标签
题目参数
时间限制 1 秒
内存限制 512 MB
提交次数 525
通过人数 273
金币数量 2 枚
难度 基础


上一题 下一题