POJ 3069 Saruman's Army（萨鲁曼军）

POJ 3069 Saruman's Army（萨鲁曼军）

Time Limit: 1000MS   Memory Limit: 65536K

【Description】

【题目描述】

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.

白袍萨鲁曼必须带领着他的军队从艾辛格径直前往圣盔谷。为了有序行军，萨鲁曼在军队中分发被称作真知晶球的远见石。每个真知晶球的最大有效范围为R个单位，并且必须由军队中的一些部队携带（即真知晶球不允许中途变动）。 通过使用最少的真知晶球来确保萨鲁曼的每个仆从都在晶球附近的R个单位内，助他掌控中土世界。

【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 x1, …, xn of each troop (where 0 ≤ xi ≤ 1000). The end-of-file is marked by a test case with R = n = −1.

输入文件有多组测试样例。 每组测试数据第一行，包括一个整数R（0 ≤ R ≤ 1000），表示真知晶球的最大有效范围，还有一个整数n（1 ≤ n ≤ 1000），表示萨鲁曼军的部队数量。 下一行有n个整数，x1， …，xn（0 ≤ xi ≤ 1000）表示每个部队的位置。 R = n = −1表示输入结束。

【Output】	【输出】
For each test case, print a single integer indicating the minimum number of palantirs needed.	对于每个测试样例，输出一个整数表示最少需要使用的真知晶球数量。

【Sample Input - 输入样例】	【Sample Output - 输出样例】
0 3 10 20 20 10 7 70 30 1 7 15 20 50 -1 -1	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.

对于第一个测试样例，萨鲁曼可以在位置10和20放置真知晶球。这样，范围为0的真知晶球可以覆盖同在位置20的部队。 对于第二个测试样例，萨鲁曼可以放置在位置7（覆盖部队1，7和15），位置20（覆盖20和30），位置50，还有位置70。这里要注意，真知晶球必须放在部队中并且不允许变动。因此，萨鲁曼不能在位置60放置真知晶球来覆盖在位置50和70的部队。

【题解】

　　贪心法，一开始还在纠结应该往前还是往后……

　　然后看了看提示的第二个测试样例……从当前位置往后贪就好了。

【代码 C++】

#include<cstdio>
#include <cstring>
#include <algorithm>
int main(){
    int r, n, i, j, data[1005], opt;
    while (scanf("%d%d", &r, &n)){
        if (r + n < 0) break;
        memset(data, 9, sizeof(data));
        for (i = 0; i < n; ++i) scanf("%d", &data[i]);
        std::sort(data, data + n);
        for (i = opt = 0; i < n; ++opt){
            for (j = i; data[j] <= data[i] + r; ++j);
            for (i = --j; data[i] <= data[j] + r; ++i);
        }
        printf("%d
", opt);
    }
    return 0;
}