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

题目链接：

题目大意：

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

思路：

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

 #include<iostream>

 #include<algorithm>

 #include<cstdio>

 #include<cstring>

 using namespace std;

 int n, r;

 int a[];

 int main()

 {

     while(scanf("%d%d", &r, &n) != EOF)

     {

         if(r < )break;

         for(int i = ; i < n; i++)scanf("%d", &a[i]);

         sort(a, a + n);

         int tot = ;

         for(int i = ; i < n; i++)

         {

             int left = a[i];

             int star = a[i];

             for(; i < n; i++)

             {

                 if(a[i] - left > r)break;

                 star = a[i];

             }

             tot++;

             i--;

             //cout<<star<<endl;

             for(; i < n; i++)

             {

                 if(a[i] - star > r)break;

             }

             i--;

         }

         cout<<tot<<endl;

     }

     return ;

 }

巴特西

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

最新文章

热门文章