POJ3122Pie（二分）

http://poj.org/problem?id=3122

题意 ：这个题最主要的就是审题要仔细，翻译不要漏句子。题目讲的是我要过生日，要给好友分馅饼（还有自己也想要一块），怕引起不公，所以每个人大小要一样，形状可以不一样，还有一句很重要，就是第一段最后那里，每个人得到的pie应该是馅饼的一块，而不是很多块零零碎碎的那种，因为那样的话就变成求平均值了 。

思路：这个理解了题意之后，就猜得到用二分了。表示一开始真的以为是求平均值来着，实际上不是，举个例子，1，2，3，三块馅饼，若每人分得的大小为2，则第一块小于2，丢弃，第二块正好等于2，第三块剩下一个1，丢弃，所以不要理解成求平均值，这个的上下界我感觉是不太好找，下界的话就是谁都分不到，上界就是每个人都有一个整的馅饼。

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>

using namespace std;

const double pi = acos(-1.0) ;
const double eps = 1e-8 ;

int main()
{
    int T ;
    scanf("%d",&T) ;
    for(int i = 0 ; i < T ; i++)
    {
        int N,F ;
        scanf("%d %d",&N,&F) ;
        F = F+1 ;
        double high = 0 ,a[11000];
        for(int j = 0; j < N ; j++)
        {
            scanf("%lf",&a[j]) ;
            a[j] = a[j]*a[j] ;
            high = max(a[j],high) ;
        }
        double low = 0.0 ;
        double mid ;
        while(high - low > eps)
        {
            int cnt = 0 ;
            mid = (low+high)/2 ;
           for(int j = 0 ; j < N ; j++)
            cnt += (int )(a[j]/mid) ;
           cnt < F?(high = mid):(low = mid );
        }
        printf("%.4lf
",pi*mid) ;//因为上边求面积的时候没有乘pi，所以这里乘上，比较方便
    }
    return 0;
}