poj 3122

题意：作者要开一个生日party，他现在拥有n块高度都为1的圆柱形奶酪，已知每块奶酪的底面半径为r不等，作者邀请了f个朋友参加了他的party，他要把这些奶酪平均分给所有的朋友和他自己（f+1人），每个人分得奶酪的体积必须相等（这个值是确定的），形状就没有要求。现在要你求出所有人都能够得到的最大块奶酪的体积是多少？

 

思路：贪心的思想+二分。复杂度为O(nlogM)，M为初始时的high-low。初始状态，上界high为每个人分得奶酪的体积sum，下界low = 0（或者是最小块的奶酪）。然后二分，每次的mid值为（low+high）/ 2，然后根据mid值（估计值）遍历n块奶酪，看看这个mid值能分给多少个人，如果份数大于等于f，表示mid偏小，low = mid，反之high = mid。

 

注意的问题： 1.数据得开double，开float的话精度不够，二分时 high - low > 0.000001 会出不来，导致

               Time Limit Exceeded，而不是因为数据要求高而超时。

             2.由于精度要求特别特别高，所以PI = 3.1415926535897932 和 high - low > 0.000001 是必

               须的，也是这道题总是WA的地方。

代码如下：

#include<iostream>
using namespace std;
const int Max = 10050;
const double PI = 3.1415926535897932;

int main()
{
    int t, n, f, i;
    double pie[Max];
    scanf("%d", &t);
    while(t--)
	{
        scanf("%d%d", &n, &f);
        f++;                             //  加上作者一人。
        double sum = 0;
        for(i = 1; i <= n; i ++)
		{
            int r;
            scanf("%d", &r);
            pie[i] = r * r;
            sum += pie[i];
        }
		
        double mid, low = 0, high = sum / f;
        while(high - low > 0.000001)
		{
            mid = (low + high) / 2;
            int count = 0;                //  count为当前mid值对应的能分给的人数。
            for(i = 1; i <= n; i ++)
                count += (int)(pie[i] / mid);  
            if(count >= f) 
				low = mid;
            else high = mid;
        }
        printf("%.4lf\n", mid * PI);
    }
    return 0;
}