POJ 3122 Pie 詳解

題目：N (≤10⁴) 個圓柱形餅乾，高 1，半徑 rᵢ。F 個朋友 + 自己共 F+1 人。每人分得同一塊餅乾切出的同體積塊（不可拼接多塊）。最大化每人體積。輸出體積（絕對誤差 ≤10⁻³）。

核心模型：二分體積 + 貪心計算可分塊數

高固定為 1，體積正比於面積（πr²）。二分面積 S（或體積 V）。
檢查函數 check(S)：對每個餅乾，可切出 floor(πrᵢ² / S) 塊。總和 ≥ F+1 則可行。
二分上界：max(πrᵢ²)（最大單餅面積）。下界：0。
精度：1e-5 足夠（輸出 4 位小數）。

優化：排序 + 提前退出

半徑降序排序。檢查時從大餅開始累加，若累計 ≥ F+1 立即返回 true。若當前餅面積 < S 則後續更小，直接 break。

參考代碼 (C++)

#include <bits/stdc++.h>
using namespace std;

const double PI = acos(-1);
const double EPS = 1e-5;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T; cin >> T;
    while (T--) {
        int N, F; cin >> N >> F;
        vector r(N);
        for (int i = 0; i < N; ++i) cin >> r[i];
        sort(r.begin(), r.end(), greater());
        double lo = 0, hi = PI * r[0] * r[0];
        while (hi - lo > EPS) {
            double mid = (lo + hi) / 2;
            int cnt = 0;
            for (double rad : r) {
                double area = PI * rad * rad;
                if (area < mid) break; // 後續更小
                cnt += (int)(area / mid);
                if (cnt >= F + 1) break;
            }
            if (cnt >= F + 1) lo = mid;
            else hi = mid;
        }
        cout << fixed << setprecision(4) << lo << '\n';
    }
    return 0;
}

關鍵測試用例

常見錯誤

• ❌ 二分上界設為總面積/(F+1) → 可能超過最大單餅面積，導致 check 永遠 false。
• ❌ 用 double 直接比較 cnt >= F+1 → 需轉 int 取整。
• ❌ 精度不夠 → 輸出 4 位小數需二分精度 1e-5 以上。
• ❌ 未排序/未提前退出 → 大數據 TLE。

複雜度分析

總結

POJ 3122 是「二分答案 + 貪心檢查」的經典應用。核心技巧：將「最大化最小份額」轉化為「給定份額檢查可行性」。排序優化與提前退出是通過大數據限制的關鍵。此模式適用於「公平分配、負載均衡、資源切分」等最大化最小值問題。