《挑战程序设计竞赛》例题：Saruman's Army

例题大意：一条直线上有n个点，并给出它们的位置，如果给其中一个点做标记，那么这个点会有一个半径为r的范围，问：让所有点都处于范围之内，最少需要标记几个点
分析：第一步肯定是先将各个点的位置排序。要求最少应该标记几个点，那么就肯定要充分利用标记点的范围，即尽可能不让标记点的范围笼罩不存在点的地方，那么就先从第一个点开始与后面的点比较，如果第n个点与第一个点位置相减要大于r，那么说明第n-1个点的范围可以笼罩到第一个点，那么就将第n-1个点标记起来，再从该点向右看，如果第k个点与第n-1个点相减要大于r，那么就确定了第n-1个点进行标记，它的笼罩范围是[1,k-1]，然后从第k个点开始重复该操作。

源代码：

#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
   while(true)
   {
       int n,r,count=0,i=0;
       cin>>r>>n;
       int a[1001];
       if(r==-1&&n==-1)break;//跳出循环的条件
       for(int i=0;i<n;i++)cin>>a[i];
       sort(a,a+n);//排序
       while(i<n)
       {
           int s=a[i++];//先将第i个点的位置储存起来，然后i++
           while(i<n&&a[i]-s<=r)i++;//如果i<n而且a[i+1]-a[i]<=r，那么就继续i++
           int flag=a[i-1];//确定标记点的位置
           while(i<n&&a[i]-flag<=r)i++;//同理从标记点开始往右看
           count++;//右边的范围也确定后就标记点数+1
       }
       cout<<count<<endl;
   }
}