POJ--3069 Saruman's Army(贪心)

记录
0:33 2023-1-24

http://poj.org/problem?id=3069

reference:《挑战程序设计竞赛(第2版)》2.2.4 p45

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.

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.

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

贪心算法，体现在不断地找到当前当前的最优策略，这里最优策略体现在，尽可能的让中心点靠后。

#include<cstdio>
#include<algorithm>
using namespace std;
#define MAX_N 10000

int N, R;
int X[MAX_N];

void solve() {
    sort(X, X + N);

    int i = 0, ans = 0;
    while (i < N) {
        int s = X[i++];

        while(i < N && X[i] <= s + R) i++;
        
        int p = X[i - 1];

        while(i < N && X[i] <= p + R) i++;

        ans++;
    }
    printf("%d\n", ans);
}

int main() {
    while (~scanf("%d %d", &R, &N)) {
        if(R == -1 && N == -1) {
            break;
        }
        for(int i = 0; i < N; i++) {
            scanf("%d", &X[i]);
        }
        solve();
    }
}