UVA 1555 Garland：二分搜尋求解燈泡高度最優解

題目大意

有 n 盞燈泡排成一排，第一盞高度固定為 A，最後一盞高度為 B（待求最小值）。相鄰三盞燈泡滿足遞推關係：
H[i] = 2*H[i-1] + 2 - H[i-2]（i ≥ 3）。
要求所有燈泡高度非負，求最小可能的 B。

解題思路：二分搜尋 + 遞推驗證

1. 自由度分析：已知 H[1]=A，H[2] 未知。一旦確定 H[2]，整條數列唯一確定。
2. 單調性：H[2] 越大，後續高度越大，B=H[n] 越大；且若某 H[2] 導致出現負高度，則更小的 H[2] 必然也會出現負高度。因此可對 H[2] 二分搜尋最小合法值。
3. 驗證函數 check(x)：設 H[2]=x，按遞推式生成至 H[n]，若過程中出現 H[i] < 0 返回失敗；否則記錄 B=H[n] 並返回成功。
4. 搜尋區間：H[2] 理論下界 -1（允許負數中轉），上界可設較大常數（如 1e6）。精度要求 1e-6，輸出保留兩位小數。

核心代碼 (C++)

#include 
using namespace std;

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

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    while (cin >> n >> A) {
        double lo = -1, hi = 1e6;
        for (int iter = 0; iter < 100; ++iter) { // 固定迭代次數保證精度
            double mid = (lo + hi) / 2;
            if (check(mid)) hi = mid;
            else lo = mid;
        }
        check(hi); // 刷新 B
        cout << fixed << setprecision(2) << B << '\n';
    }
    return 0;
}

關鍵點總結

• 遞推公式推導正確是前提。
• 二分搜尋對象是 H[2] 而非 B，利用單調性縮小搜尋空間。
• 雙精度浮點數足夠，固定 100 次迭代遠超 1e-6 精度需求。
• 輸出格式 %.2lf / setprecision(2) 符合題目要求。