UVa 12097 - Pie(二分查找) 发表于 2015-08-29 | 分类于 AOAPC Training Guide , Chapter 1. Algorithm Design , General Problem Solving Techniques | 给出n、m,有n个蛋糕,m+1个人,每个蛋糕都可以切开,求每人分一整块蛋糕的最大值。求出蛋糕大小总和,然后进行二分查找,对二分的值进行验证。12345678910111213141516171819202122232425262728293031323334353637#include<cstdio>#include<cmath>using namespace std;const double EPS=1e-6;const double PI=acos(-1);const int maxn=10010;int n,f;double a[maxn];inline double c(double r){ return PI*r*r;}bool ok(double x){ int sum=0; for(int i=0;i<n;++i){ sum+=floor(a[i]/x); } return sum>=f+1;}int main(){ int t;scanf("%d",&t); while(t--){scanf("%d%d",&n,&f); double sum=0; for(int i=0;i<n;++i){ scanf("%lf",&a[i]); a[i]=c(a[i]); sum+=a[i]; } double l=0,r=sum,m=(l+r)/2; while(r-l>EPS){ if(ok(m)) l=m; else r=m; m=(l+r)/2; } printf("%.4f\n",m); } return 0;}本文迁移自我的 CSDN博客 ,格式可能有所偏差。