YT15 完整解析：二分答案求最大等體積派對切分

N 個圓柱體派對（高度 1，半徑 rᵢ），F 位朋友 + 自己共 F+1 人。每人分得一塊（可來自不同派對，但不可拼接），求最大可能體積 V。誤差 ≤ 1e-3。

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

派對體積 Vᵢ = π × rᵢ² × 1 = π rᵢ²。
二分答案 V，檢查能否切出 ≥ F+1 塊體積 ≥ V 的派對：

bool check(double V) {
    int cnt = 0;
    for (int i = 0; i < N; i++)
        cnt += (int)(volume[i] / V); // 每個派對能切多少塊
    return cnt >= F + 1;
}

完整 AC 程式碼

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

const double PI = acos(-1.0);
double vol[10010];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int T; cin >> T;
    while (T--) {
        int N, F; cin >> N >> F;
        double sum = 0;
        for (int i = 0; i < N; i++) {
            int r; cin >> r;
            vol[i] = PI * r * r; // 高度=1
            sum += vol[i];
        }
        
        double L = 0, R = sum / (F + 1);
        for (int iter = 0; iter < 60; iter++) { // 60 次二分足夠 1e-18 精度
            double mid = (L + R) / 2;
            int cnt = 0;
            for (int i = 0; i < N; i++) cnt += (int)(vol[i] / mid);
            if (cnt >= F + 1) L = mid;
            else R = mid;
        }
        
        cout << fixed << setprecision(4) << L << '\n';
    }
    return 0;
}

關鍵點總結

• 體積公式：圓柱體積 = πr²h，h=1 簡化為 πr²
• 二分上界：總體積 / (F+1)，平均分配極限
• 整數除法：(int)(vol[i] / V) 自動向下取整，對應不可拼接限制
• 精度控制：固定 60 次迭代或 R-L > 1e-6，輸出 4 位小數滿足 1e-3 誤差
• 時間複雜度：O(T × N × log(精度)) ≈ 10000 × 60 極快