Pie POJ - 3122【贪心、二分】

该题连接

    这是一道英文题，所以这里就不放原题了，我写一下它的题意：

        主人要开一个party，而主人有N个派，他要宴请F个人（也就是要有F+1个人要吃派），但这些人又很挑剔，他们每个人吃派只吃一种派，并且还不能容忍其他人吃的派比自己多。

    所以这就是一道二分，我们假设每个人吃到的派的体积为v，那么对于给定的每一个派Ai，我们切割成v的体积可以切割出（Ai/v）个，如果对于切割得到的数目num，假如num<F+1，则相当于不够吃，要减小分配的体积，反之亦正确。然后这里的判断有个小插曲，我们用到“num<F+1”而不是“num>F+1”来判断是有原因的，这和它的条件有着密不可分的关系，因为当num==F+1的时候，也是可以在尝试往下继续分的。

二分操作主要代码：

        double l=0, r=maxn, mid=(l+r)/2;
        while(r-l>0.000001)
        {
            mid=(l+r)/2;
            int num=0;
            for(int i=1; i<=N; i++)
            {
                num+=(int)(a[i]/mid);
            }
            if(num<F)
            {
                r=mid;
            }
            else
            {
                l=mid;
            }
        }

AC代码：

#include <iostream>
#include <cstdio>
#include <algorithm>
#define pi 3.14159265358979
using namespace std;
int N,F;
double a[10005];
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d %d",&N, &F);
        F++;
        int ri;
        double maxn=-1;
        for(int i=1; i<=N; i++)
        {
            scanf("%d",&ri);
            a[i]=pi*ri*ri;
            if(maxn<a[i])maxn=a[i];
        }
        double l=0, r=maxn, mid=(l+r)/2;
        while(r-l>0.000001)
        {
            mid=(l+r)/2;
            int num=0;
            for(int i=1; i<=N; i++)
            {
                num+=(int)(a[i]/mid);
            }
            if(num<F)
            {
                r=mid;
            }
            else
            {
                l=mid;
            }
        }
        printf("%.4lf\n",r);
    }
    return 0;
}