ACM 競賽經典：切派問題的二分查找解法 (NWERC 2006)

題目來源：2006 ACM 西北歐區域賽 Problem C。核心挑戰：給定 N 個半徑不同的圓柱形派（高度均為 1），需分給 F 位朋友加自己共 F+1 人，每人獲得體積相等、形狀不限的單一塊派，求最大可能體積 V。

問題建模

• 每個派體積 V_i = π * r_i^2（高度 1）。
• 若目標塊體積為 x，第 i 個派可切出 floor(V_i / x) 塊。
• 總塊數 sum >= F+1 則 x 可行；單調性明顯：x 越大，可切塊數越少。

二分查找策略

1. 搜索區間 [0, max(V_i)]。
2. 中點 mid = (L + R) / 2，檢查 ok(mid)。
3. 若可行（sum >= F+1），L = mid；否則 R = mid。
4. 精度要求 1e-3，迭代條件 R - L > 1e-5 保證輸出 %.4f 正確。

完整代碼 (C++)

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

const int MAXN = 10010;
const double PI = acos(-1.0);
double area[MAXN];
int N, F;

bool check(double x) {
    int cnt = 0;
    for (int i = 0; i < N; ++i)
        cnt += (int)(area[i] / x);
    return cnt >= F + 1;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T; cin >> T;
    while (T--) {
        cin >> N >> F;
        double maxA = 0;
        for (int i = 0; i < N; ++i) {
            int r; cin >> r;
            area[i] = PI * r * r;
            maxA = max(maxA, area[i]);
        }
        double L = 0, R = maxA;
        while (R - L > 1e-5) {
            double M = (L + R) / 2;
            if (check(M)) L = M;
            else R = M;
        }
        printf("%.4f\n", L); // 題目要求誤差 1e-3，輸出 4 位小數穩妥
    }
    return 0;
}

關鍵點總結

• 二分查找不僅用於有序陣列查找，更適用於「單調性決策問題」。
• 浮點數二分終止條件用區間長度而非固定次數，更直觀可控精度。
• floor 運算對應整數除法截斷，C++ 中 (int)(a/b) 等效。
• 時間複雜度 O(N log(maxA/eps))，N, F ≤ 10000 極易通過。

樣例驗證

Input:
3
3 3
4 3 3
1 24
5 10
5 1 4 2 3 4 5 6 5 4 2

Output:
25.1327
3.1416
50.2655

第一組：3個派半徑 4,3,3，面積約 50.27, 28.27, 28.27，4人分，最大塊 ≈ 25.13 (π*4^2/2)。