POJ 3069 Saruman's Army（贪心）

传送门

这个题是说给你n个点，然后让你标记其中尽可能少的点，使得n个点都处于被标记点左右不超过R的区间内

我们使用的是贪心算法，也就是我们要将被标记的点尽可能的朝右边去即可，首先我们将他们从左到右进行排序，第一个我们所选取的被标记的点应该是能够包含掉左边的点的最靠右的点。。。

假设s是我们还没有被包含进去的最左边的点，那么我们要一直往右找到最右边的那个能够将这个点包含进去的点；等我们找到了它，我们就将它所能包含进去的点全部跳过，这样我们就能得到下一个还没有被包含进去的最左边的点。
 

#include<cstdio>
#include<algorithm>
using namespace std;
int main()
{
    int r,n,a[10010];
    while(scanf("%d %d",&r,&n) != EOF)
    {
        if(r == -1 && n == -1)
            break;
        for(int i = 0;i < n; i++)
            scanf("%d",&a[i]);
        sort(a,a + n);
        int i = 0,ans = 0;
        while(i < n)
        {
            int s = a[i++];
            while(i < n && a[i] <= s + r)
                i++;
            int p = a[i-1];
            while(i < n && a[i] <= p + r)
                i++;
            ans++;
        }
        printf("%d\n",ans);
    }
    return 0;
}