POJ_3069 Saruman's Army 【贪心】

一、题面

POJ3069

二、题意分析

我的理解是，可以在每个点设置一个监测点，能够监测到范围R内的所有其他点，那么问给出N个点的一维位置，需要在其中挑多少个监测点把所有点都监测到。

贪心解决：

　　1.先排序。

　　2.考虑第一个点，因为每个点是必须要监测的，那么第一个点需要被监测到，它可以是监测点，也可以是被监测点。贪心的想，为了能监测更多的点，让第一个点作为被监测的点，且是监测范围内最边界上的点。

　　3.现在需要考虑，当第一个点往右探测R范围时，最后一个点将是需要设置的监测点。

　　4.以这个监测点再往右扫R范围。

　　5.完成了一个监测点及其范围内点的覆盖。后面的点类似处理。

三、AC代码

 #include <cstdio>

 #include <iostream>

 #include <algorithm>

 using namespace std;

 const int MAXN = 1e3;

 int Data[MAXN+], N, R;

 int solve()

 {

     int i = , ans = , cur;

     while(i < N)

     {

         cur = Data[i++];

         while(i < N && Data[i] <= cur+R)

             i++;

         cur = Data[i-];

         while(i < N && Data[i] <= cur + R)

             i++;

         ans++;

     }

     return ans;

 }

 int main()

 {

     freopen("input.txt", "r", stdin);

     while(scanf("%d %d", &R, &N) != EOF && R != -)

     {

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

             scanf("%d", &Data[i]);

         sort(Data, Data+N);

         printf("%d\n", solve() );

     }

     return ;

 }

巴特西

POJ_3069 Saruman's Army 【贪心】

一、题面

二、题意分析

最新文章

热门文章