HDU 1969 Pie [二分]

1.题意：一项分圆饼的任务，一堆圆饼共有N个，半径不同，厚度一样，要分给F+1个人。要求每个人分的一样多，圆饼允许切但是不允许拼接，也就是每个人拿到的最多是一个完整饼，或者一个被切掉一部分的饼，要求你算出每人能分到的饼的体积最大值。输入数据依次给出，测试数据组数T，每组数据中，给出N，F，以及N个圆饼的半径。输出最大体积的数值，精确到小数点后四位。

2.分析:一看是这种输出就知道用二分写会很高效，这里对"能分出的最大体积值"进行二分。首先，这个值有界，最大值为总体积除以总人数的值，即ΣV/(F+1),最小值不妨设为0，然后在二分过程中判断mid值的大小，具体做法为：以mid"分割"N个圆饼，记录一个圆饼最多能分出多少个mid，最后统计一组圆饼能分出的mid数的总和cnt，接着对cnt讨论，cnt<F+1,mid大了，现有的饼分不出那么多，所以向上二分，cnt>=F+1，向下二分,大于小于都好理解，关键是cnt等于F+1时，此时以mid划分正好分出了F+1个，那么这就直接得到答案了么？分析一下，cnt==F+1，包含了mid偏小的情况，因为在此mid上增加一点有可能cnt不变。最后，由于输出格式为小数点后四位，所以当[l , r]，这个区间的长度小于1e-5时就可以退出二分了。

Tips：Pi选用acos(-1.0),输出为%.4f,不然会WA 的

3.代码如下：

 # include <iostream>

 # include <cstdio>

 # include <cmath>

 using namespace std;

 const double EPS=1e-;

 const int MAXN=;

 const double PI=acos(-1.0);

 int T,N,F;

 int R[MAXN];

 int sgn(double x)

 {

     if(fabs(x)<EPS) return ;

     if(x<) return -;

     else return ;

 }

 bool judge(double mid)

 {

     int cnt=;

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

         cnt+=(int)((R[i]*R[i]*PI)/(mid));

     //printf("cnt=%d\n",cnt);

     if(cnt<F+) return true;

     else return false;

 }

 void Init()

 {

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

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

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

 }

 void Solve()

 {

     double r=;

     double l=;

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

         r+=PI*R[i]*R[i];

     r=r/(double)(F+);

     while(sgn(fabs(r-l)-(1e-))>=)

     {

         //printf("%.5f %.5f ",l,r);

         double mid=(l+r)/2.0;

         //printf("%.5f\n",mid);

         if(judge(mid)) r=mid;

         else l=mid;

     }

     printf("%.4f\n",l);

 }

 int main()

 {

     scanf("%d",&T);

     while(T--)

     {

         Init();

         Solve();

     }

     return ;

 }

巴特西

HDU 1969 Pie [二分]

最新文章

热门文章