HDUOJ1969 二分法求解最大值

    原题链接：
    题      意：(F+1)个人分享烙饼，要保证每个人(共N个人)分得的体积是一样的，每分得的一块要么是原本就存在的一整块，要么就是由原来交大的分割而来，不能是由两块或两块以上的饼拼凑而来。试求每个人能分得的最大的烙饼的体积。
    方      法：二分法
    分      析：①首先可知每个人能获得的饼的最小体积和最大体积分别是：0，MAX(pie[0], pie[1],......pie[n-1]),在保证每块饼都不是拼凑而来的情况下，能获得的饼的体积的单调不连续递增的;
                ②令 left = 0, right = max, middle = (left + right)/2;    //left right middle 均为饼的体积
                ③函数 test() 的作用是测试当前所得饼的体积(middle)是否已是能分割的极限，看更大体积的饼是否能被分割出来。
    代      码：

#include<stdio.h>
#include<math.h>

#define PI    acos(-1.0)

double pie[10008];

int test(double x, int n, int f)
{
    int sum = 0;

    for(int i = 0; i < n; i++)
    {
        sum += (int)(pie[i] / x);
    }

    if(sum >= f + 1)        //还能在分
    {
        return 1;
    }
    else
    {
        return 0;
    }
}

int main(void)
{
    int t;
    int n, f;

    double l, r, m;

    double max;

    scanf("%d", &t);
    while(t--)
    {
        max = 0;
        scanf("%d%d", &n, &f);
        for(int i = 0; i < n; i++)
        {
            scanf("%lf", pie + i);
            pie[i] = pie[i] * pie[i] * PI;

            max = max > pie[i] ? max : pie[i];
        }

        l = 0;
        r = max;
        m = (l + r) / 2.0;

        while(l - r < -1e-6)
        {
            if(test(m, n, f))                //还可再分
            {
                l = m;
            }
            else
            {
                r = m;
            }

            m = (l + r) / 2.0;
        }

        printf("%.4lf\n", m);
    }

    return 0;
}

AC要注意的几个问题：① π = acos(-1.0) 是比较精确的
                        ② l - r < -1e-6 注意精度