【题目描述】

小明的生日要到了！根据习俗，他需要将一些派分给大家。

他有 $$N 个不同口味、不同大小的派。有 $F$ 个朋友会来参加我的派对，每个人会拿到一块派（必须一个派的一块，不能由几个派的小块拼成；可以是一整个派）。

我的朋友们都特别小气，如果有人拿到更大的一块，就会开始抱怨。因此所有人拿到的派是同样大小的（但不需要是同样形状的），虽然这样有些派会被浪费，但总比搞砸整个派对好。当然，我也要给自己留一块，而这一块也要和其他人的同样大小。

请问我们每个人拿到的派最大是多少？每个派都是一个高为 $1$，半径不等的圆柱体。

【输入描述】

第一行包含两个正整数 n$N$ 和m $F$，表示派的数量和朋友的数量。（N>=1, F<=10000）

第二行包含 $N$ 个 1 到 $10000$ n之间的整数，表示每个派的半径

【输出描述】

输出每个人能得到的最大的派的体积，精确到小数点后三位。

【样例输入】

3 3 

4 3 3

【样例输出】

25.133

【题目分析】

• 比较标准的二分
  

• 注意题目中的第一个坑，N个不同的派，要分给F+1个人(因为包含自己)

• 精确到小数点后三位，说明左右区间的判断不再是整数，需要参考上一道题 切割绳子 的写法。

• 由原来的 直线改成圆柱体了，题目中求圆柱的体积的方法需要记住。

• 圆周率在此题中不能取3.14。因为题目要求保留3位小数，所以要么取3.1415926。要么用  acos(-1.0)来表示圆周率

【思路】

读入所有派的半径，这个过程中求出最大的体积作为max。然后开始 二分，用mid 来分蛋糕，按照分成的数量来决定区间端点。

【参考答案】

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<iomanip>
#include<cmath>
using namespace std;
const double pi=acos(-1.0);// acos(-1.0)就是求-1.0的反余弦，经计算，acos(-1.0) 的值就是圆周率
//const double pi=3.1415926; //也可以这样定义
const int MAXX=100009;
double a[MAXX];
bool ok(double);
int n,f;
int main() {
	int T;
	double maxx=0;
	scanf("%d%d",&n,&f);
	for(int i=0; i<n; i++) {
		int r;
		scanf("%d",&r);
		a[i]=pi*r*r;//每个派的面积
		maxx=max(maxx,a[i]);//找到这里面的最大值作为右端点
	}
	double l=0,r=maxx;
	while(r-l>1e-5) { //精确 二分答案的套路过程
		double m=(l+r)/2;
		if(solve(m))
			l=m;//扩大范围，看看每个人能不能分到更多
		else
			r=m;
	}
	printf("%.3lf",l);//printf格式化输出会自动四舍五入；
	return 0;
}
bool solve(double s) { //每人是否能分面积s的派
	int sum=0;
	for(int i=0; i<n; i++) {
		sum+=floor(a[i]/s);//向下取整，分不到s的浪费；
	}
	return sum>=f+1;//能否分到
}