POJ - 3069 - Saruman's Army - 芒果糕

POJ - 3069 - Saruman's Army - 芒果糕
http://poj.org/problem?id=3069

Saruman the White must lead his army along a straight path from Isengard to Helm’s Deep. To keep track of his forces, Saruman distributes seeing stones, known as palantirs, among the troops. Each palantir has a maximum effective range of R units, and must be carried by some troop in the army (i.e., palantirs are not allowed to “free float” in mid-air). Help Saruman take control of Middle Earth by determining the minimum number of palantirs needed for Saruman to ensure that each of his minions is within R units of some palantir.

Input

The input test file will contain multiple cases. Each test case begins with a single line containing an integer R, the maximum effective range of all palantirs (where 0 ≤ R ≤ 1000), and an integer n, the number of troops in Saruman’s army (where 1 ≤ n ≤ 1000). The next line contains n integers, indicating the positions x₁, …, x_n of each troop (where 0 ≤ x_i ≤ 1000). The end-of-file is marked by a test case with R = n = −1.

Output

For each test case, print a single integer indicating the minimum number of palantirs needed.

Sample Input

0 3
10 20 20
10 7
70 30 1 7 15 20 50
-1 -1

Sample Output

2
4

Hint

In the first test case, Saruman may place a palantir at positions 10 and 20. Here, note that a single palantir with range 0 can cover both of the troops at position 20.
In the second test case, Saruman can place palantirs at position 7 (covering troops at 1, 7, and 15), position 20 (covering positions 20 and 30), position 50, and position 70. Here, note that palantirs must be distributed among troops and are not allowed to “free float.” Thus, Saruman cannot place a palantir at position 60 to cover the troops at positions 50 and 70.

http://mangogao.com/read/300.html
给出n个点的坐标，从这n个点中标记若干个点。对每个点，半径为r的范围内必须有带标记的点。
在这个条件下，求最少需要标记多少个点。

从最左侧的点开始考虑，要让这个点符合要求，则其右侧r范围内必须有点被标记，为了标记最少的点，这个被标记的点应该是r范围内最右侧的点。标记了这个点后，其右侧r范围内无需考虑。然后将下一个点作为最左侧的点，这样一直贪心下去，即可求出最后答案。
bool a[2020];

int main() {
#ifndef ONLINE_JUDGE
    freopen("data.in", "r", stdin);
#endif

    int r, n, x;
    while (cin >> r >> n && r != -1) {
        memset(a, 0, sizeof(a));
        while (n--) {
            cin >> x;
            a[x] = 1;
        }
        int ans = 0;
        for (int i = 0; i <= 1000; i++) {
            if (!a[i]) continue;
            int nx = i + r;
            while (nx >= 0 && !a[nx]) nx--;
            ans++;
            i = nx + r;
        }
        cout << ans << endl;
    }

    return 0;
}

挑战上的解法，这题也可以把所有坐标存下来，排序后再进行处理。最开始不考虑这种方法是因为想到要去重，但实际上重复是不影响的，因为每次都是找符合要求的最右侧一个点，重复的数据都会跳过。
int a[1010];

int main() {
#ifndef ONLINE_JUDGE
    freopen("data.in", "r", stdin);
#endif

    int r, n, x;
    while (scanf("%d%d", &r, &n) && r != -1) {
        for (int i = 0; i < n; i++)
            scanf("%d", &a[i]);
        sort(a, a + n);
        int i = 0, ans = 0;
        while (i < n) {
            // 找到最左侧的点s
            int s = a[i++];
            // 一直走到第一个距离s大于r的点
            while (i < n && a[i] <= s + r) i++;
            // p是需要标记的点
            int p = a[i - 1];
            // 一直走到第一个距离p大于r的点
            while (i < n && a[i] <= p + r) i++;
            // 标记点数加1
            ans++;
        }
        cout << ans << endl;
    }

    return 0;
}

https://xuanwo.org/2014/08/25/POJ-3069-Saruman's-Army/
Read full article from POJ - 3069 - Saruman's Army - 芒果糕