POJ 3122-Pie(二分+精度)

题目地址:

题意：给出n个pie的直径。有F+1个人，假设给每人分的大小同样（形状能够不同），每一个人能够分多少。要求是分出来的每一份必须出自同一个pi(既当pie大小为3。2，1，仅仅能分出两个大小为2的份，剩下两个要扔掉。)

思路：对每个人分的大小进行二分。

注意讲pi放在最后成。能够提高精度。

Ps:wa了5发。不知道错在哪，然后把输出的%lf改成%f就A了，并不知道为什么。。。sad

#include <stdio.h>

#include <math.h>

#include <string.h>

#include <stdlib.h>

#include <iostream>

#include <sstream>

#include <algorithm>

#include <set>

#include <queue>

#include <stack>

#include <map>

using namespace std;

typedef long long LL;

const int inf=0x3f3f3f3f;

const double pi= acos(-1.0);

const double esp=1e-6;

const int maxn=10010;

double a[maxn];

int main()

{

    int T,n,F;

    scanf("%d",&T);

    while(T--){

        double low=0,high=0;

        scanf("%d %d",&n,&F);

        F+=1;

        for(int i=0;i<n;i++){

            scanf("%lf",&a[i]);

            a[i]=a[i]*a[i];

            high=max(high,a[i]);

        }

        double mid;

        int cnt;

        while(high-low>esp){

            cnt=0;

            mid=(low+high)/2;

            for(int i=0;i<n;i++)

                cnt+=(int)(a[i]/mid);

            if(cnt>=F){

                low=mid;

            }

            else

                high=mid;

        }

        printf("%.4f\n",mid*pi);

    }

    return 0;

}