Pie

题目解析

二分答案题目。我们需要在连续的实数域上二分体积。

1 题目解析：单调性证明（反证法）

我们定义一个检查函数 check(V)：能否将 $N$ 个派切分出至少 $F+1$ 块（朋友+我自己），且每块体积为 $V$ 。

命题：该问题具有单调性。即：如果体积 $V$ 是合法的（check(V) == true），那么任何比 $V$ 小的体积 $V^{′}$ 也一定是合法的。

证明（反证法）：

假设：存在一个体积 $V$ 满足 check(V) == true，但存在一个更小的体积 $V^{′}<V$ 使得 check(V') == false。
分析：
- 对于第 $i$ 个派，其体积为 $S_{i}$ 。
- 能切出体积为 $V$ 的块数为 $\left⌊S_{i}/V\right⌋$ 。
- 所有派能切出的总块数为 $K=\sum_{i=1}^{N} \left⌊S_{i}/V\right⌋$ 。
- 根据前提 check(V) == true，我们知道 $K\ge F+1$ 。
推导：
- 因为 $V^{′}<V$ ，所以 $\frac{1}{V^{′}}>\frac{1}{V}$ 。
- 进而对于任意派 $S_{i}$ ，有 $\frac{S_{i}}{V^{′}}>\frac{S_{i}}{V}$ 。
- 由于向下取整函数 $\left⌊x\right⌋$ 是单调不减的，所以 $\left⌊S_{i}/V^{′}\right⌋\ge \left⌊S_{i}/V\right⌋$ 。
- 对所有派求和，得出 $V^{′}$ 对应的总块数 $K^{′}\ge K$ 。
矛盾：
- 既然 $K\ge F+1$ ，且 $K^{′}\ge K$ ，那么必然 $K^{′}\ge F+1$ 。
- 这意味着 check(V') 必须为 true。
- 这与假设（check(V') == false）矛盾。
结论：假设不成立，单调性得证。我们可以使用二分法找到最大的 $V$ 。

--------------------V ------------------
       ^
       |
       |
  V'---+

核心: 证明: 如果V' 不合法,所有的 x < V' 都不合法

2 代码实现

根据你的模板进行了适配。注意：

原模板是针对整数二分的（寻找第一个满足条件的位置），本题是浮点数二分（寻找最大可行值），逻辑有细微差别。
人数需要算上自己，所以是 $F+1$ 。
$\pi$ 使用 acos(-1.0) 获得高精度值。

cpp

/**
 * Author by Rainboy blog: https://rainboylv.com github : https://github.com/rainboylvx
 */
#include <cstdio>
#include <cmath>
#include <algorithm> // 包含 std::max
using namespace std;

// POJ 3122 Pie
// 只需要 cstdio 和 cmath，不需要 iostream 和 iomanip

const int maxn = 10005; 
int n, f;
double area[maxn]; // 直接存储体积(面积)

// const double PI = 3.1415926535897932; 
// 精度建议更高一点，或者使用 acos(-1.0)
const double PI = acos(-1.0);

bool check(double val) {
    int count = 0;
    // 总人数是 f + 1 (朋友 + 自己)
    int target = f + 1;
    
    // 注意：这里使用 0 到 n (左闭右开)
    for(int i = 0; i < n; i++) {
        count += (int)(area[i] / val);
        if (count >= target) return true;
    }
    return false;
}

double bs_find(double l, double r) {
    // 循环100次通常比 while(r-l > eps) 更稳定且更快
    for(int i = 0; i < 100; i++){
        double mid = (l + r) / 2.0;
        if(check(mid)) {
            l = mid; 
        } else {
            r = mid;
        }
    }
    return l; 
}

void solve() {
    // 1. 使用 scanf
    scanf("%d %d", &n, &f);
    
    double max_vol = 0;
    
    // 2. 修正循环：从 0 到 n-1，与 check 函数保持一致
    for(int i = 0; i < n; i++) {
        int r;
        scanf("%d", &r);
        
        // 计算面积
        area[i] = PI * r * r;
        
        // 3. 修正最大值的获取逻辑 (二分的右边界)
        if(area[i] > max_vol) max_vol = area[i];
    }

    // 二分范围：0 到 最大那块派的体积
    double ans = bs_find(0, max_vol);
    
    // 4. 使用 printf 输出，保留4位小数
    printf("%.4f\n", ans);
}

int main () {
    int t;
    scanf("%d", &t); // 使用 scanf
    while(t--) {
        solve();
    }
    return 0;
}

代码简要说明

mid 函数：修改为浮点数除法 (l+r)/2.0。
check 函数：
- 核心逻辑：遍历所有派，计算每个派能切出多少个体积为 val 的块（floor(派体积 / val)）。
- 累加总块数，判断是否大于等于 f + 1（题目要求每个人都要有，包括自己）。
bs_find 函数：
- 使用了固定次数循环（for i < 100）来代替精度判断 while(r-l > eps)。这是解决几何/浮点二分题目的常用技巧（Magic Number 100），可以避免精度卡死循环的问题，且 100 次二分后精度极高。
- 逻辑：如果 check(m) 成立，说明这个体积可以分给所有人，我们贪心地尝试更大的体积，所以 l = m。否则 r = m。
main 函数：处理多组测试用例 T。

cpp

/**
 * Author by Rainboy blog: https://rainboylv.com github : https://github.com/rainboylvx
 */
#include <cstdio>
#include <cmath>
#include <algorithm> // 包含 std::max
using namespace std;

// POJ 3122 Pie
// 只需要 cstdio 和 cmath，不需要 iostream 和 iomanip

const int maxn = 10005; 
int n, f;
double area[maxn]; // 直接存储体积(面积)

// const double PI = 3.1415926535897932; 
// 精度建议更高一点，或者使用 acos(-1.0)
const double PI = acos(-1.0);

bool check(double val) {
    int count = 0;
    // 总人数是 f + 1 (朋友 + 自己)
    int target = f + 1;
    
    // 注意：这里使用 0 到 n (左闭右开)
    for(int i = 0; i < n; i++) {
        count += (int)(area[i] / val);
        if (count >= target) return true;
    }
    return false;
}

double bs_find(double l, double r) {
    // 循环100次通常比 while(r-l > eps) 更稳定且更快
    for(int i = 0; i < 100; i++){
        double mid = (l + r) / 2.0;
        if(check(mid)) {
            l = mid; 
        } else {
            r = mid;
        }
    }
    return l; 
}

void solve() {
    // 1. 使用 scanf
    scanf("%d %d", &n, &f);
    
    double max_vol = 0;
    
    // 2. 修正循环：从 0 到 n-1，与 check 函数保持一致
    for(int i = 0; i < n; i++) {
        int r;
        scanf("%d", &r);
        
        // 计算面积
        area[i] = PI * r * r;
        
        // 3. 修正最大值的获取逻辑 (二分的右边界)
        if(area[i] > max_vol) max_vol = area[i];
    }

    // 二分范围：0 到 最大那块派的体积
    double ans = bs_find(0, max_vol);
    
    // 4. 使用 printf 输出，保留4位小数
    printf("%.4f\n", ans);
}

int main () {
    int t;
    scanf("%d", &t); // 使用 scanf
    while(t--) {
        solve();
    }
    return 0;
}

疑问

为什么不能用 while ( r-l > eps) ?

其实并不是完全不能用 while (r - l > eps)，在逻辑上它是对的。

但在算法竞赛（尤其是像 POJ 这种老式评测机，或者处理几何/浮点数二分时），强烈推荐使用 for(int i=0; i<100; i++) 这种固定次数的写法。

主要原因有以下三点：

1. 精度死循环风险 (最重要)

计算机中的 double 是有精度极限的（大约 15-16 位有效数字）。当 l 和 r 非常非常接近时（例如数值很大，但差值很小），由于浮点数的密度限制，(l + r) / 2.0 计算出的 mid 可能会因为精度丢失，**直接等于 l 或者等于 r**。

如果你的代码逻辑是 l = mid，而 mid 因为精度问题算出来等于 l，那么 l 就永远不会变，循环条件 r - l > eps 永远满足，程序就会陷入死循环 (TLE)。

例子：假设 eps 设为 1e-10，但当前区间是 [1000000.00000000001, 1000000.00000000002]。计算机可能无法表示这两个数中间的数，导致 mid 始终无法让区间缩小到 eps 以下。

2. `eps` 很难选准

如果 eps 设得太大（比如 1e-4），题目要求保留 4 位小数，可能因为精度不够导致 Wrong Answer (WA)。
如果 eps 设得太小（比如 1e-12），就可能触发上面的“精度死循环”导致 Time Limit Exceeded (TLE)。

每次做题都要去纠结 eps 到底该设多少，很麻烦。

3. 固定循环次数绝对安全且精度足够

二分法的本质是指数级缩小区间。循环 100 次，区间会缩小为初始长度的。

这意味着，哪怕你的初始范围是整个宇宙的大小，二分 100 次后，精度也能精确到一个原子的大小。这个精度（级别）远远超过了 double 类型本身能存储的精度（double 只有左右）。

所以，写成这样是“降维打击”：

cpp

// 只需要无脑循环 100 次
for(int i = 0; i < 100; i++) {
    double mid = (l + r) / 2;
    if(check(mid)) l = mid;
    else r = mid;
}

这样做：

绝对不会死循环（循环次数是固定的）。
精度绝对够用（远超题目要求的小数点后4位）。
不用费心思考 eps 设多少。

总结

在 POJ 3122 这道题中，用 while(r - l > 1e-8) 大概率也是能过的，因为这道题的数据范围还不至于触发精度死锁。但为了养成良好的比赛习惯，防止在更刁钻的题目上翻车，固定循环次数是更优的工程实践。

目录