Pie————二分+尺取练习-蒲公英云

Pie————二分+尺取练习

给你n个蛋糕的半径，你有m个朋友，所以总共有m+1个人，现在要分蛋糕，要求每个人分到的大小都是一样的，且每个人的蛋糕都是从一块上切割下来的（不能是2个不同的蛋糕拼起来的），现在问每个人最多能分到多少蛋糕（体积），保留到小数点后4位输出。

Input
第一行是组数T，接下来是T组数据。
每组数据包含2行，第一行是n和m，均不超过10000，参考描述。
第二行是n个数，每个数表示一个蛋糕的半径，均不超过10000.

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

Hint
比如第二组
1 24
5
表示有一个半径是5的蛋糕，所以体积是25pi，现在你们有1+24个人分，每人能分到pi

找最大的蛋糕，进行二分

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const double PI=acos(-1.0); 
const int MAXN=1e4+9;
int t,n,F;
double l,r,mid;
double a[MAXN];
bool cmp(double a,double b)
{
    return a>b;
}
int judge(double mid)
{
    int ans=0;
    for(int i=0;i<n;i++)
    {
        ans+=int (a[i]/mid);
        if(ans>F)   return 1;
    }
    return 0;
}
int main()
{
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d %d",&n,&F);
        for(int i=0;i<n;i++)
        {
            scanf("%lf",&a[i]);
            a[i]=a[i]*a[i]*PI;
        }
        sort(a,a+n,cmp);
        l=0;
        r=a[0];
        while(r-l>1e-5)
        {
            mid=(l+r)/2.0;
            if(judge(mid))  l=mid;
            else            r=mid; 
        }
        printf("%.4f\n",l);
    }
    return 0;
}