原题 : http://poj.org/problem?id=3122
//poj 3122 //题意:我有n块圆柱体形状的蛋糕,他们的半径大小不一,现在我来了m个朋友，我要切蛋糕给他们，要求每块蛋糕的大小相同,求出每个人可以分到的蛋糕的最大体积 // 每个人分到的必须是一块，不能是由两小块拼凑起来的。 // 给出蛋糕的数目,朋友的数目以及每块蛋糕的半径，求出结果 //思路:二分+贪心。设最大那块蛋糕的体积为r,最小是l(l=0),则结果的范围是已知的，即l~r,用二分查找mid=(l+r)/2; // 每次得到mid，检查mid是否合法。方式：假设mid是结果，求出最多可以切成多少块mid大小的蛋糕，再和人数m比较。 // 逐渐缩小区间，直到求出结果 //注意①精度问题,不让调用库函数的PI....PI的值要足够精确 ②题目给出的人数是朋友的人数，还应该加上自己,自己也要吃 ③题目给出的是蛋糕的半径不是体积 #include<iostream> #include<cstdio> #include<algorithm> using namespace std; double pie[10001]; int n,m; const double PI=3.1415926535898;//圆周率要准，3.1415926535898 int check(double per) { int cnt=0; for(int i=0;i<n;i++) { cnt=cnt+(int)(pie[i]/per); } if(cnt>=m){ //合法 return 1; } return 0;//不合法 } int cmp(double a,double b) { return a<b; } int main() { int t; scanf("%d",&t); while(t--) { scanf("%d %d",&n,&m); m=m+1; //加上自己 for(int i=0;i<n;i++) { scanf("%lf",&pie[i]); pie[i]=PI*pie[i]*pie[i]*10000;//精度处理 } sort(pie,pie+n,cmp); double r=pie[n-1]; double l=0;//得到结果的范围 double rs;//存放结果值 while(l<=r)//二分 { double mid=(l+r)/2; if(check(mid)){ rs=mid; l=mid+0.01; }else{ r=mid-0.01; } } printf("%.4lf\n",rs/10000); } return 0; } //AC
