#OJ2189. 级简单题
级简单题
级简单题
Time Limit: 1 Sec Memory Limit: 128 MB
Description
直线上有N个点。点i的位置是xi。从这N个点中选择若干个,给他们加上标记。对每一个点,其距离为R以内(小于等于R)的区域里必须有带有标记的点(自己本身带有标记,可以认为与其距离为0的地方有一个带标记的点)。在满足这个条件的情况下,希望能为尽可能少的点添加标记。请问至少要有多少点被加上标记? 限制条件 1.1<=N<=1000 2.0<=R<=1000 3.0<=x<=1000
Input
第一行输入N和R 第二行输入每个点的坐标,不一定是排好序的
Output
Sample Input
3 0
10 20 20
Sample Output
2