UVA 10382 Watering Grass：貪心區間覆蓋噴頭選擇

UVA 10382 Watering Grass：貪心區間覆蓋噴頭選擇

矩形草坪 L×W，n 個噴頭位於長邊上（坐標 x，半徑 r）。噴頭有效覆蓋寬度為 2√(r² - (W/2)²)（半徑 > W/2 才有效）。求最少噴頭覆蓋全長 L。

幾何轉區間

噴頭中心 x，有效覆蓋區間 [x - d, x + d]，其中 d = √(r² - W²/4)。問題轉化為：給定區間集合，最少選幾個覆蓋 [0, L]。

貪心區間覆蓋算法

1. 過濾無效噴頭（r ≤ W/2）。
2. 計算有效區間 [left, right]，按 left 升序排序。
3. 當前覆蓋到 cur，在所有 left ≤ cur 的區間中選 right 最大者，更新 cur = maxRight，計數++。
4. 重複直到 cur ≥ L 或無可用區間。

完整代碼（C++）

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;

struct Interval { double l, r; } a[11000];

bool cmp(Interval a, Interval b) { return a.l < b.l; }

int main() {
    int n; double L, W;
    while (scanf("%d%lf%lf", &n, &L, &W) == 3) {
        int cnt = 0;
        for (int i = 0; i < n; i++) {
            double x, r; scanf("%lf%lf", &x, &r);
            if (r <= W/2) continue;
            double d = sqrt(r*r - W*W/4);
            a[cnt++] = {x - d, x + d};
        }
        sort(a, a+cnt, cmp);
        int ans = 0; double cur = 0;
        for (int i = 0; i < cnt; ) {
            double maxR = 0;
            while (i < cnt && a[i].l <= cur) {
                maxR = max(maxR, a[i].r);
                i++;
            }
            if (maxR <= cur) break; // 無法延伸
            ans++; cur = maxR;
            if (cur >= L) break;
        }
        if (cur >= L) printf("%d\n", ans);
        else printf("-1\n");
    }
    return 0;
}

關鍵點

• 幾何推導：噴頭圓與草坪矩形交集的投影長度。
• 區間排序後貪心選擇，證明最優。
• 邊界：cur 初始 0，區間 left ≤ cur 才可選。
• 輸出 -1 表示無法覆蓋。

複雜度

• 時間：O(n log n)，排序主導。
• 空間：O(n)。

此題是「幾何問題轉區間覆蓋」的經典範例，展示了跨領域建模與貪心算法的威力。