【题目描述】

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

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

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

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

【输入描述】

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

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

【输出描述】

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

【样例输入】

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;//能否分到  }

(adsbygoogle = window.adsbygoogle || []).push({});