【题目链接】
【题目考点】
1. 二分答案
2. 实数域二分查找
【解题思路】
二分答案问题。
题目求的是每人得到的一块派的最大体积。
考虑需要满足什么条件。有
f
f
f个朋友，加上自己，一共
f
+
1
f+1
f+1个人，每人都要有一块派，可以浪费。那么也就是说分出的派的块数要大于等于
f
+
1
f+1
f+1。
分出的派的数量受原有派大小的限制，假设某个派体积为pv，每人分到的一块派体积为v，那么这个派可以分出
?
p
v
/
v
?
\lfloor pv/v \rfloor
?pv/v?块派。
按照这种方法求出所有派能切分出的块数，看得到的块数是否大于等于
f
+
1
f+1
f+1。
综上，该二分答案问题为：求满足得到派的块数大于等于
f
+
1
f+1
f+1的每块派的体积的最大值。
该题为实数域二分查找问题。
【注意】：本题精度要求比较高，一般来说，精确到小数点后3位，写r-l >= 1e-4即可，而该题需要写到r-l >= 1e-5。这种情况也是可能存在的。竞赛时，精度可以写得高一些。
【题解代码】
解法1：二分答案
#include <bits/stdc++.h>
using namespace std;
#define N 10005
const double PI = acos(-1);
double pv[N];//派的体积
int n, f;
bool check(double v)//如果每人得到体积v的派，那么可以分成的块数是否大于等于f
{
int s = 0;
for(int i = 1; i <= n; ++i)
s += int(pv[i] / v);
return s >= f;
}
int main()
{
cin >> n >> f;
f++;//实际人数为f+1
double rad, tot = 0;//tot：所有派的总体积
for(int i = 1; i <= n; ++i)
{
cin >> rad;//第i个派的半径
pv[i] = PI * rad * rad * 1;//第i个派的体积：底面积乘以高
tot += pv[i];
}
double l = 0, r = tot/f, m;//l:最小的体积 r:最大的体积 tot是体积和。每人能分到的最大体积也就是tot/f。
int num;
while(r - l >= 1e-5)//本题精度要求比较高 需要差值小于1e-5
{
m = (l + r) / 2;
if(check(m))//如果每块为m，能否得到大于等于f块。如果块数足够，应该增大体积
l = m;
else//如果块数不够，应该减小体积
r = m;
}
cout << fixed << setprecision(3) << m;
return 0;
}
