NYOJ 6：噴水裝置——貪心區間覆蓋問題

問題描述

草坪 20m × 2m，噴頭安裝在橫向中心線上（y=1），每個噴頭覆蓋半徑 R 的圓。給定 n 個噴頭半徑 (0 < R < 15)，保證能完全覆蓋草坪。求最少啟用多少個噴頭使整個草坪濕潤。多組測試數據。

幾何轉化：區間覆蓋

草坪寬 2m，中心線距邊緣 1m。噴頭半徑 R 在中心線上，其覆蓋草坪的水平投影為長度 2 * sqrt(R² - 1²) 的區間（勾股定理）。問題轉化為：在長度 20 的線段上，用最少數量的給定區間覆蓋 [0, 20]。

貪心策略

1. 計算每個噴頭的有效覆蓋長度 len = 2 * sqrt(R*R - 1)（若 R ≤ 1 則 len=0，無效）。
2. 將 len 降序排序（大半徑優先）。
3. 從左到右貪心選取：當前未覆蓋位置 pos=0，每次選覆蓋最遠的噴頭（即最大 len），pos += len，計數++，直到 pos ≥ 20。
4. 因題目保證可覆蓋，必有解。

代碼實現

#include <stdio.h>
#include <math.h>
#define MAXN 610

float r[MAXN];

int main() {
    int m; scanf("%d", &m);
    while (m--) {
        int n; scanf("%d", &n);
        for (int i = 0; i < n; i++) scanf("%f", &r[i]);
        // 計算有效覆蓋長度並降序排序
        float len[MAXN];
        int cnt = 0;
        for (int i = 0; i < n; i++) {
            if (r[i] > 1) len[cnt++] = 2 * sqrt(r[i]*r[i] - 1);
        }
        sort(len, len+cnt, greater());
        // 貪心覆蓋
        float covered = 0;
        int ans = 0;
        for (int i = 0; i < cnt && covered < 20; i++) {
            covered += len[i];
            ans++;
        }
        printf("%d\n", ans);
    }
    return 0;
}

原代碼邏輯解析

原代碼將半徑升序排序，從最大半徑開始往回累加 x -= sqrt(r[i]*r[i] - 1)，其中 x 初始為 10（半長）。等價於上述貪心，但更巧妙：
x 表示剩餘半長度，每次用最大半徑覆蓋 sqrt(R²-1)，直到 x ≤ 0。答案為 n - i（已用噴頭數）。

關鍵點

• 半徑 ≤ 1 的噴頭無法覆蓋寬度 2 的草坪，直接忽略。
• 浮點數運算，注意精度：用 double 更穩妥。
• 排序後貪心取大半徑最優，因覆蓋長度單調遞增，大半徑性價比最高。