糯米

TI DaVinci, gstreamer, ffmpeg
随笔 - 167, 文章 - 0, 评论 - 47, 引用 - 0
数据加载中……

POJ 3122 Pie 二分

可以看出,达到最大size的时候一定是某个蛋糕刚好被分完,如果再大一点的话,肯定就不能解决了。
比这个size小,则无论如何都可以解决。

所以可以通过二分答案的方法来解决这个问题。就很简单了。
注意:这题精度要求很高,pi的值需要通过acos(-1)来求,eps要到e-5。
我用C++提交能够AC,g++一直WA。
吗的,数据能不能宽容点。

#include <stdio.h>
#include 
<math.h>
#include 
<algorithm>

using namespace std;

int N, F;
double pi = acos(-1.0);
double pie[10032];
double sum, maxp;

int main()
{
    
double l, r, m;
    
int i, t, c;

    scanf(
"%d"&t);
    
while (t--{
        scanf(
"%d%d"&N, &F); 
        F
++;
        maxp 
= sum = 0;
        
for (i = 0; i < N; i++{
            scanf(
"%d"&c);
            pie[i] 
= c*c*pi;
            maxp 
= max(maxp, pie[i]);
            sum 
+= pie[i];
        }

        l 
= maxp / F;
        r 
= sum / F;
        
while (l + 0.00001 < r) {
            m 
= (l + r) / 2;
            c 
= 0;
            
for (i = 0; i < N; i++)
                c 
+= floor(pie[i] / m);
            
if (c < F)
                r 
= m;
            
else
                l 
= m;
        }

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


    
return 0;
}








posted on 2011-02-23 14:46 糯米 阅读(437) 评论(0)  编辑 收藏 引用 所属分类: POJ


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理