Pie

实数二分

#include<stdio.h>
#include<math.h>
double PI = acos(-1.0);                     //cos Π = -1  ===>  acos(-1) = Π  
#define eps 1e-5                            //试试eps多小会超时，多大会Wrong Answer
double area[10010];                         //每个蛋糕的独立面积
int n,m;
bool check(double mid){ 
  int sum = 0;
  for(int i=0;i<n;i++)                      //把每个圆蛋糕都按大小mid分开。统计总数
    sum += (int)(area[i] / mid);            //每个蛋糕整除mid
  if(sum >= m) return true;                 //最后看总数够不够m个
  else return false;
}
int main(){
  int T; scanf("%d",&T);                    //测试例子
  while(T--){
    scanf("%d%d",&n,&m); m++;               //蛋糕数量，朋友+1
    double maxx = 0;
    for(int i=0;i<n;i++){
      int r; scanf("%d",&r);                //蛋糕半径
      area[i] = PI*r*r;                     //蛋糕面积
      if(maxx < area[i]) maxx = area[i];    //最大的一块蛋糕
    }
    double left = 0, right = maxx; 
    for(int i = 0; i<100; i++){             //for循环的次数，试试多小会Wrong Answer
  //while((right-left) > eps) {             //用while循环做二分
      double mid = left+(right-left)/2;
      if(check(mid)) left = mid;            //每人能分到mid大小的蛋糕
      else right = mid;                     //不够分到mid大小的蛋糕
    }
    printf("%.4f\n",left);                  // 打印right也对，right-left < eps
  }
  return 0;
}

笔记：实数二分的精度控制很重要，循环少了达不到题目要求精度，多了就延长运行时间导致超时，计算分蛋糕千万别忘记算上生日主角，每人分到的蛋糕是必须一整块，就算分到两块完整的蛋糕也是错误的