首页 > 代码库 > HDU 1969 Pie 二分

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

3.代码如下:

 1 # include <iostream>
 2 # include <cstdio>
 3 # include <cmath>
 4 using namespace std;
 5 const double EPS=1e-8;
 6 const int MAXN=10005;
 7 const double PI=acos(-1.0);
 8 int T,N,F;
 9 int R[MAXN];
10 int sgn(double x)
11 {
12     if(fabs(x)<EPS) return 0;
13     if(x<0) return -1;
14     else return 1;
15 }
16 bool judge(double mid)
17 {
18     int cnt=0;
19     for(int i=0;i<N;i++)
20         cnt+=(int)((R[i]*R[i]*PI)/(mid));
21     //printf("cnt=%d\n",cnt);
22     if(cnt<F+1) return true;
23     else return false;
24 }
25 void Init()
26 {
27     scanf("%d%d",&N,&F);
28     for(int i=0;i<N;i++)
29         scanf("%d",&R[i]);
30 }
31 void Solve()
32 {
33     double r=0;
34     double l=0;
35     for(int i=0;i<N;i++)
36         r+=PI*R[i]*R[i];
37     r=r/(double)(F+1);    
38     while(sgn(fabs(r-l)-(1e-5))>=0)
39     {
40         //printf("%.5f %.5f ",l,r);
41         double mid=(l+r)/2.0;
42         //printf("%.5f\n",mid);
43         if(judge(mid)) r=mid;
44         else l=mid;
45     }
46     printf("%.4f\n",l);
47 }
48 int main()
49 {
50     scanf("%d",&T);
51     while(T--)
52     {
53         Init();
54         Solve();
55     }
56     return 0;
57 }

 

HDU 1969 Pie 二分