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

缺乏、安全感 2022-05-17 19:59 179阅读 0赞

给你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;
    }