【小数二分】

题目：3122 -- Pie (poj.org)

题意：

有n个派，f+1个人，给每个人分一块同样体积的派，可以破坏派，问每个人分得的派的最大体积为多少，答案保留四位小数。

题解：采用小数二分做（第一次接触到小数二分的题，注意小数二分与整数二分的不同）

代码：

#include<cstdio>
#include<cmath>
#define PI acos(-1.0)
using namespace std;
int n,friendsnum;
double a[10010],maxsize,cul;
int judge(double size){	
	 int sum=0;
	 for(int i=0;i<n;i++)
	 {
	 	 sum+=(int)(a[i]/size);
	 	 if(sum>=friendsnum) return 1;
	 }
	 return 0;
}
double binary_search(){
	 double high=cul/friendsnum,low=maxsize/friendsnum;
	 double size=(high+low)/2;
	 while(high-low>0.0000001)
	 {
	 	 if(judge(size)) low=size;
	 	 else high=size;
		 size=(high+low)/2;
	 }
	 return size;	 
}
int main(){
	 int t;
	 scanf("%d",&t);
	 while(t--)
	 {
	 	 maxsize=0;cul=0;
	 	 scanf("%d%d",&n,&friendsnum);
	 	 friendsnum++;
	 	 int temp;
	 	 for(int i=0;i<n;i++) 
		 {
			 scanf("%d",&temp);
			 a[i]=(temp*temp*PI);
			 cul+=a[i];
			 if(maxsize<a[i]) maxsize=a[i];
	 	 }
	 	 double answer=binary_search();
	 	 printf("%.4f\n",answer);
	 }
	 return 0;
}