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+3], N, R;

int solve()
{
    int i = 0, ans = 0, cur;
    while(i < N)
    {
        cur = Data[i++];
        while(i < N && Data[i] <= cur+R)
            i++;
        cur = Data[i-1];
        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 != -1)
    {
        for(int i = 0; i < N; i++)
            scanf("%d", &Data[i]);
        sort(Data, Data+N);
        printf("%d
", solve() );
    }
    return 0;
}