POJ 3122 Pie：二分答案 + 貪心判定最大化派分配體積

問題描述

N 個圓柱派 (高=1，半徑 r_i)，F 個朋友 + 自己共 F+1 人。每人分一塊（同一派可切多塊，但每塊必須完整來自某派）。所有人分到體積相等，求最大體積。誤差 ≤ 10⁻³。

二分答案模型

• 派體積：V_i = π × r_i²
• 若每人分體積 V，第 i 派可切 floor(V_i / V) 塊
• 總塊數 ≥ F+1 可行
• 單調性：V 越大，可切塊數越少 → 二分查找最大可行 V

完整代碼

#include 
#include 
#include 
using namespace std;

const double PI = acos(-1.0);
const double EPS = 1e-6;
double vol[10005];
int N, F;

bool check(double v) {
    if (v < EPS) return true;
    int cnt = 0;
    for (int i = 0; i < N; ++i)
        cnt += (int)(vol[i] / v);
    return cnt >= F + 1;
}

int main() {
    int T; scanf("%d", &T);
    while (T--) {
        scanf("%d%d", &N, &F);
        double maxR = 0;
        for (int i = 0; i < N; ++i) {
            int r; scanf("%d", &r);
            vol[i] = PI * r * r;
            maxR = max(maxR, vol[i]);
        }
        double lo = 0, hi = maxR;
        for (int iter = 0; iter < 50; ++iter) {  // 固定迭代次數保證精度
            double mid = (lo + hi) / 2;
            if (check(mid)) lo = mid;
            else hi = mid;
        }
        printf("%.4f\n", lo);
    }
    return 0;
}

關鍵細節

1. 體積預計算：`π r²` 存入 double 陣列
2. 二分上界：最大派體積
3. 固定迭代 50 次：`2^-50 ≈ 1e-15` 遠超 `1e-3` 要求
4. check 函數：`floor(vol/v)` 累加，注意 `v` 可能極小導致除零 → `v < EPS` 直接真
5. 輸出格式：`%.4f` 保留 4 位小數，題目要求誤差 `1e-3`

複雜度

• 每 check：O(N)
• 二分：O(N log(精度)) ≈ 50N
• N=10,000 總操作 5e5，瞬間完成

延伸：整數二分避免浮點

將體積擴大 10000 倍轉為整數，但 double 精度足夠且代碼更簡潔。