题目链接

Saruman’s Army POJ - 3069

思路

笔者曾做过本题三四次，这次再做还是无从下手觉得麻烦，但是笔者发现了一种比较通用的方法，就是状态转移。

先排序再贪心。

我们把贪心的每一步分为3种状态分别表示为

state == 0 ：表示还未确定左端点

state == 1：表示还未确定中心点

state == 2：表示已经确定中心点

转移关系如下

状态0即state == 0 时，给答案加入贡献，此时左端点可以确定，并给中心点设初值，转移到下一步的状态1

状态1即state == 1时，如果中心点可以更新则更新并转移到下一步的状态1，如果不能更新则转移到当前步的状态2

状态2即state == 2时，如果当前点能被中心点所在半径覆盖则转移到下一步的状态2,否则转移到本步的状态0

时间复杂度

$$ O(Nlog(N)) $$

代码

#include <cstdio>
#include <algorithm>

using namespace std;

const int MAXN = 1000 + 10;

int r, n;
int a[MAXN];

int main() {
    while (scanf("%d%d", &r, &n), r + n != -2) {
        for (int i = 1; i <= n; i++) {
            scanf("%d", &a[i]);// don't forget &
        }
        sort(a + 1, a + 1 + n);

        int state = 0;
        int l, mid;
        int ans = 0;
        for (int i = 1; i <= n; i++) {
            if (state == 0) {
                ans++;
                l = a[i];
                mid = a[i];
                state = 1;
            } else if (state == 1) {
                if (a[i] - l <= r) {
                    mid = a[i];
                } else {
                    state = 2;
                    i--;
                }
            } else if (state == 2) {
                if (a[i] - mid > r) {
                    state = 0;
                    i--;
                }
            }
        }
        printf("%d\n", ans);
    }

    return 0;
}