(step4.1.2)hdu 1969(Pie——二分查找)

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

题目大意:n块馅饼分给m+1个人，每个人的馅饼必须是整块的，不能拼接，求最大的。

解题思路:

1）用总饼的体积除以总人数，得到每个人最大可以得到的V.但是每个人手中不能有两片或多片拼成的一块饼。

代码如下:

/*
* 1969_2.cpp
*
* Created on: 2013年8月14日
* Author: Administrator
*/#include <stdio.h>
#include <math.h>
#include <string.h>double V[10001];
int N,F;//PI尽量用反余弦函数来算,否则可能精度不够
const double PI = acos(-1.0);/**
* 输入饼的面积，判断能否够分
* 若以此面积分割后所得的饼的块数>=人数，则够分
* 否则不够分
*/
bool test(double x){//num .用来记录三块大馅饼最终能分成多少个小馅饼
int num = 0;
int i;
for( i = 1 ; i <= N ; ++i){//V[i]/x 。计算每块馅饼能分成多少个小馅饼.其中的int体现了"每个人手中的馅饼不能是拼接而成的"
num += int(V[i]/x);
} //判断小馅饼数与朋友数的大小
if( num >= F){
return true;
}else {
return false;
}
}int main(){int t;
scanf("%d",&t);
while(t--){
memset(V,0,sizeof(V));
scanf("%d%d",&N,&F); F = F+1;
int i;
double sum = 0;
for( i = 1 ; i <= N ; ++i){
int r;
scanf("%d",&r);
V[i] = PI*r*r;
sum += V[i];
} double max = sum/F; double l = 0;
double r = max;
double mid ;
while( r - l > 1e-6){//注意这里的精度问题
mid = (r+l)/2; if(test(mid)){
l = mid;
}else{
r = mid;
}
} printf("%.4lf\n",(l+r)/2); }
}