NYOJ 12 噴水裝置（二）：貪心區間覆蓋經典題

問題描述

草坪尺寸 w × h，橫向中心線上有 n 個噴頭（n ≤ 10000）。第 i 個噴頭位於 (x_i, 0)，噴灑半徑 r_i，覆蓋圓形區域。選擇最少噴頭使整個草坪完全被覆蓋（即中心線段 [0, w] 被噴頭在中心線上的投影區間覆蓋）。無解輸出 0。

幾何轉化：圓 → 區間

噴頭覆蓋圓心 (x_i, 0)、半徑 r_i。要覆蓋草坪邊緣 y = ±h/2，需 r_i ≥ h/2。
在中心線 y=0 上的投影區間為：

d = sqrt(r_i² - (h/2)²)  // 勾股定理
區間 = [x_i - d, x_i + d]

貪心策略：區間覆蓋問題

經典問題：給定區間集合，選最少區間覆蓋 [0, w]。
最優策略：

1. 按區間左端點升序排序（左端點相同按右端點降序）。
2. 從左向右掃描，維護當前覆蓋右端點 cur_right。
3. 在所有左端點 ≤ 當前覆蓋右端點的區間中，選右端點最大的，更新覆蓋。
4. 重複直到覆蓋 ≥ w 或無可用區間。

完整代碼實現

#include 
#include 
#include 

#define N 100005

struct Interval {
    double l, r;  // 左端點、右端點
} f[N];

int cmp(const void* a, const void* b) {
    struct Interval* A = (struct Interval*)a;
    struct Interval* B = (struct Interval*)b;
    if (A->l < B->l) return -1;
    if (A->l > B->l) return 1;
    return (B->r < A->r) ? -1 : 1;  // 左端點相同，右端點大的在前
}

int main() {
    int T, n, i, j;
    double w, h, x, r;
    scanf("%d", &T);
    while (T--) {
        scanf("%d%lf%lf", &n, &w, &h);
        h /= 2;  // 半高
        
        // 讀入並轉換為區間
        for (i = 0, j = 0; i < n; i++) {
            scanf("%lf%lf", &x, &r);
            if (r < h) continue;  // 半徑不足，無法覆蓋邊緣
            double d = sqrt(r*r - h*h);
            f[j].l = x - d;
            f[j].r = x + d;
            j++;
        }
        n = j;  // 有效噴頭數
        
        qsort(f, n, sizeof(f[0]), cmp);
        
        double cur_right = 0, next_right = 0;
        int cnt = 0;
        
        // 第一步：覆蓋起點 0
        for (i = 0; i < n; i++) {
            if (f[i].l > 0) break;  // 左端點已超過 0，無法覆蓋起點
            if (f[i].r > cur_right) cur_right = f[i].r;
        }
        if (cur_right == 0) {  // 無法覆蓋起點
            printf("0\n");
            continue;
        }
        cnt = 1;
        
        // 貪心擴展覆蓋
        for (; i < n; i++) {
            if (cur_right >= w) break;  // 已覆蓋終點
            
            if (f[i].l <= cur_right) {  // 可接上當前覆蓋
                if (f[i].r > next_right) next_right = f[i].r;
            }
            
            if (f[i].l > cur_right) {  // 需要選擇下一個區間
                if (f[i].l > next_right) {  // 有間隙，無法覆蓋
                    cnt = 0;
                    break;
                }
                cnt++;
                cur_right = next_right;
                next_right = 0;
            }
        }
        
        // 邊界檢查
        if (cur_right < w) {
            if (next_right < w) cnt = 0;
            else cnt++;
        }
        
        printf("%d\n", cnt);
    }
    return 0;
}

關鍵邏輯詳解

1. 區間生成過濾

• r < h/2：噴頭半徑不足以覆蓋草坪寬度，直接丟棄。
• d = sqrt(r² - (h/2)²)：投影半長度。

2. 排序規則

• 主鍵：l 升序。
• 次鍵：r 降序（左端點相同時，覆蓋範圍大的優先）。

3. 兩階段掃描

4. 邊界情況處理

• 無法覆蓋起點：cur_right == 0 → 輸出 0。
• 中間有間隙：f[i].l > cur_right && f[i].l > next_right → 輸出 0。
• 循環結束後：若 cur_right < w，檢查 next_right 是否能補上最後一段。

複雜度分析

• 時間：O(n log n)（排序主導），n ≤ 10000 瞬間通過。
• 空間：O(n)。

樣例驗證

輸入：
2
2 8 6
1 1
4 5
2 10 6
4 5
6 5

第1組：h=3，噴頭1: r=1<3 棄；噴頭2: r=5, d=4, 區間[0,8] 覆蓋[0,8] → 1個
第2組：h=3，噴頭1: r=5, d=4, 區間[0,8]；噴頭2: r=5, d=4, 區間[2,10]
排序：[0,8], [2,10]
初始：cur_right=8 (選[0,8])
擴展：i=1, l=2≤8, next_right=10
結束：cur_right=8<10, next_right=10≥10 → cnt=2

輸出：
1
2  ✓

總結

NYOJ 12 是區間貪心覆蓋的教科書級應用。核心步驟：

1. 幾何條件轉化為一維區間（圓投影 + 勾股定理）。
2. 過濾無效噴頭（半徑不足）。
3. 排序 + 貪心兩階段掃描（初始化覆蓋起點 + 擴展覆蓋）。
4. 精細處理邊界（起點、間隙、終點）。

此模板適用於「攝像頭覆蓋」「基站選址」「雷達佈防」等所有最少資源覆蓋線段問題。