POJ-3069 Saruman's Army---区间选点

题目链接：

题目大意：

在一条直线上，有n个点。从这n个点中选择若干个，给他们加上标记。对于每一个点，其距离为R以内的区域里必须有一个被标记的点。问至少要有多少点被加上标记。

思路：

我们从最左边的开始考虑。对于这个点，到距其R以内的区域必须要有带有标记的点。带有标记的点一定在其右侧（包含这个点本身）。给从最左边开始，距离为R以内的最远的点加上标记，尽可能的覆盖更靠右边的点。对于添加了标记的点右侧相距超过R的下一个点，采用同样的方法找到最右侧R距离以内最远的点添加标记。在所有点都被覆盖之前不断重复这一过程。

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<cstdio>
 4 #include<cstring>
 5 using namespace std;
 6 
 7 int n, r;
 8 int a[1005];
 9 
10 int main()
11 {
12     while(scanf("%d%d", &r, &n) != EOF)
13     {
14         if(r < 0)break;
15         for(int i = 0; i < n; i++)scanf("%d", &a[i]);
16         sort(a, a + n);
17         int tot = 0;
18         for(int i = 0; i < n; i++)
19         {
20             int left = a[i];
21             int star = a[i];
22             for(; i < n; i++)
23             {
24                 if(a[i] - left > r)break;
25                 star = a[i];
26             }
27             tot++;
28             i--;
29             //cout<<star<<endl;
30             for(; i < n; i++)
31             {
32                 if(a[i] - star > r)break;
33             }
34             i--;
35         }
36         cout<<tot<<endl;
37     }
38     return 0;
39 }