python/TangDou/AcWing/TiaoZhanChengXuSheJi/POJ3069.cpp

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

int r, n, X[1100];
int ans;
int main() {
#ifndef ONLINE_JUDGE
    freopen("POJ3069.in", "r", stdin);
#endif
    while (cin >> r >> n && ~r && ~n) {
        ans = 0;
        for (int i = 0; i < n; i++) cin >> X[i];
        sort(X, X + n);

        int i = 0;
        while (i < n) {
            int s = X[i++];                     // s:没有被覆盖的最左边点的位置
            while (i < n && X[i] <= s + r) i++; // 找到无法覆盖的点
            int p = X[i - 1];                   // 新加上标注点的位置
            while (i < n && X[i] <= p + r) i++; // 将此点右侧，所有可覆盖的点走完
            ans++;
            /*
            Q:为什么一定要执行两次while呢?不能是一次while吗？
            答：本题贪心的逻辑：排完序，标注点越往后越好，这样使的标点最少。
            ① 算法逻辑就是一路向前，找到一个大于规则半径R的序号，然后，回退一个，在这个位置上安排一个。
            ② 这个位置上安排完了，它可以照亮后面的R个范围，需要一路向前进行排除。
            ③ 到达了一个无法覆盖的位置，那么必须在这里安排一个标注点吗？当然不是，因为我们是贪心的，越往后越好，
            左边已经照顾不到它了，但它的右边可以照顾它啊！所以第二个while循环登场~
            */
        }
        printf("%d\n", ans);
    }
    return 0;
}