POJ 3122 Pie （二分）

Description

Input

Output

Sample Input

3
3 3
4 3 3
1 24
5
10 5
1 4 2 3 4 5 6 5 4 2

Sample Output

25.1327
3.1416
50.2655

题意

每个pie都是高为1的圆柱体，输入这N个pie的半径，要公平地把pie分给每一个人，所有人得到pie的尺寸一样，但是形状可以不同，并且每一个人得到的pie必须来源于一个pie。

就是说如果有3个pie, 尺寸分别为1,2,3。

如果要给每人尺寸为2的pie，那么最多分给2个人，而不是3个人

因为第一个pie尺寸为1，小于2，扔掉

第二个pie尺寸为2，等于2，刚好分给一个人

第三个pie尺寸为3，切出尺寸为2的一份，分给一个人，剩下的尺寸为1的就扔掉

思路

我们知道圆的面积与其半径的平方成正比例，因此给每一个人分配的大小便与所有pie半径平方直接相关咯！

又因为每一个人不可以同时从两个pie得到属于自己的那部分，所以我们可以固定当前所要分给每个人的半径，然后判断所有的pie，是否可以刚好分给所有人，若满足，可以尝试增大半径，若不满足，尝试减小半径，所以在这里采用二分的思想。

AC 代码

#include <stdio.h>
#include <math.h>
#define PI 3.1415926535897932

double a[10050];
int n,f;
void solve(double sum)
{
    double low=0,high=sum/f;    //high是当前pie平均分配时的值，也就是最大值
    while(high-low>1e-8)    //二分
    {
        double mid = (low+high)/2.0;
        int count=0;
        for(int i=0; i<n; i++)  //判断每一个pie看可以分成几个块
            count+=(int)(a[i]/mid);
        if(count>=f)low=mid;
        else high=mid;
    }
    printf("%.4lf\n",low*PI);
}

int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        double sum=0.0;
        scanf("%d%d",&n,&f);
        ++f;    //加上他自己
        for(int i=0; i<n; i++)
        {
            scanf("%lf",a+i);
            a[i]*=a[i];     //计算平方，因为圆的面积与半径平方成正比例
            sum+=a[i];      //总的半径平方和
        }
        solve(sum);
    }
    return 0;
}