uvalive 3635 Pie

https://vjudge.net/problem/UVALive-3635

题意：

有F+1个人要分n个蛋糕，他们得到的蛋糕的面积必须是一样的，但是每个蛋糕必须是整块的蛋糕，而不是有多块蛋糕拼成的，蛋糕的形状也可以不相同。

给出n块蛋糕各自的半径，求他们每个人能得到的蛋糕的最大面积。

思路：

使得最小值最大，那显然是二分。

二分半径，计算面积，然后枚举每个蛋糕，计算每个蛋糕可以分出来的当前面积的蛋糕会有多少个，总数是否大于等于F+1即可。

记住计算个数的时候要用floor向下取整函数，而且l从0开始枚举（因为人数可能比蛋糕个数多），r从半径的最大值开始枚举就行了。

代码：

 #include <stdio.h>

 #include <math.h>

 #include <algorithm>

 using namespace std;

 const double pi = acos(-1.0);

 int a[];

 int n,f;

 bool meet(double r)

 {

     double area = pi * r * r;

     long long sum = ;

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

     {

         double one = pi * a[i] * a[i];

         sum += (int)floor(one / area);

         //printf("%f %f %d\n",one,area,(int)floor(one / area));

     }

     return sum >= f;

 }

 int main()

 {

     int t;

     scanf("%d",&t);

     while (t--)

     {

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

         f++;

         int maxn = -;

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

         {

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

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

         }

         sort(a,a+n);

         double l = ,r = maxn;

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

         {

             double mid = (l + r) / ;

             if (meet(mid)) l = mid;

             else r = mid;

         }

         printf("%.5lf\n",l * pi * l);

     }

     return ;

 }