UVA 1555 Garland：二分答案求燈泡最小高度

題目大意

n 個燈泡懸掛，首尾高度固定為 A、B。中間燈泡高度滿足遞推：H[i] = 2·H[i-1] + 2 - H[i-2]。要求所有高度 ≥ 0，求最小可能的 B。

數學推導

已知 H[0]=A，設 H[1]=x (未知)。遞推得：

H[2] = 2x + 2 - A
H[3] = 2(2x+2-A) + 2 - x = 3x + 6 - 2A
H[4] = 4x + 12 - 3A
...
H[k] = k·x + k(k-1) - (k-1)A

實際不需通項公式，直接遞推模擬即可。x 單調影響所有 H[i]，故可二分 x。

二分檢查函數

bool check(double x) {
    H[0] = A;
    H[1] = x;
    for (int i = 2; i < n; i++) {
        H[i] = 2*H[i-1] + 2 - H[i-2];
        if (H[i] < 0) return false;  // 違反非負約束
    }
    B = H[n-1];
    return true;
}

完整 C++ 代碼

#include 
#include 
#include 
using namespace std;

const int MAXN = 1500;
int n;
double A, B, H[MAXN];

bool check(double x) {
    H[0] = A;
    H[1] = x;
    for (int i = 2; i < n; i++) {
        H[i] = 2*H[i-1] + 2 - H[i-2];
        if (H[i] < 0) return false;
    }
    B = H[n-1];
    return true;
}

int main() {
    while (scanf("%d%lf", &n, &A) != EOF) {
        double l = -1, r = 1e6;  // 搜索範圍足夠大
        while (r - l > 1e-6) {
            double mid = (l + r) / 2;
            if (check(mid)) r = mid;
            else l = mid;
        }
        printf("%.2lf\n", B);
    }
    return 0;
}

關鍵點分析

數學本質

遞推關係 H[i] - H[i-1] = H[i-1] - H[i-2] + 2，即一階差分等差數列，公差為 2。故 H[i] 為關於 i 的二次多項式，凸函數。最小 B 對應最小合法 x，即某 H[i] 剛好觸及 0 的情況。

複雜度

• 單次 check：O(n)
• 二分次數：log₂((r-l)/eps) ≈ 30
• 總計：O(n log precision)，n≤1000 瞬間出結果

測試樣例

Input:
3 100
Output:
100.00  (等腰三角形，中間最高)

Input:
4 10
Output:
16.00   (經過計算驗證)

總結

經典「二分答案」題型：目標值 B 隨參數 x 單調變化，檢查函數可線性驗證。關鍵在於證明單調性、設定合理搜索邊界、精度控制。此類問題廣泛存在於物理模擬、幾何優化、資源分配等領域。