POJ 3069 Saruman's Army：貪心算法解決區間覆蓋問題

題目重述

直線上有 N 個部隊位置 x₁…xₙ，每個掌心石覆蓋範圍 R（即 [p-R, p+R]），且掌心石必須放在部隊位置上。求最少需要多少掌心石使所有部隊被覆蓋。

貪心策略證明

1. 將部隊位置排序。
2. 從最左未被覆蓋的部隊 s 開始，掌心石應放在能覆蓋 s 的最右部隊位置 p（即最大的 xᵢ ≤ s+R）。
3. 該掌心石覆蓋範圍為 [p-R, p+R]，標記所有落入此範圍的部隊為已覆蓋。
4. 重複直到所有部隊覆蓋。

最優性證明：任何最優解中，覆蓋最左部隊的掌心石位置可右移至 p 而不減少覆蓋範圍，故貪心選擇不劣於最優解。

C++ 實作

#include 
using namespace std;
const int MAXN = 1005;
int X[MAXN];

int main() {
    int R, N;
    while (cin >> R >> N, R != -1 || N != -1) {
        for (int i = 0; i < N; ++i) cin >> X[i];
        sort(X, X + N);
        int ans = 0, i = 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;
        }
        cout << ans << endl;
    }
    return 0;
}

關鍵點

• 排序後線性掃描，時間 O(N log N)。
• 掌心石必須放在部隊位置，故 p = X[i-1] 而非 s+R。
• 樣例 1：R=0, 位置 10,20,20 → 答案 2（20 放一顆覆蓋兩部隊）。