poj 3122 hdu 1969 Pie

点击打开链接poj 3122

点击打开链接hdu' 1969

思路：二分
分析：
1 题目说的是有n块圆形的饼，饼的高度都是1但是半径不一定相同。现在有f+1个人（算上自己），想要平均分得一块面积相同的饼，必须是一块不能够是组合起来的，问这f+1个人能够分到的最大的面积是多少
2 很明显的二分ans，然后对n块饼进行判断，利用二分逼近的思想求出ans
3 注意这样一题的精度要求很高，pi = 3.1415926535898，还有eps不能取太小会TLE。

代码：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;

#define MAXN 10010
#define pi 3.1415926535898
#define eps 1e-6

int t , N , F;
double sum;
double r[MAXN];

void solve(){
   double left , right , mid;
   left = 0;
   right = 1.0*(pi*sum)/F;
   while(right-left > eps){
      mid = left+(right-left)/2.0;
      
      int count = 0;
      for(int i = 0 ; i < N ; i++){
         double s = pi*r[i]*r[i];
         int tmp = s/mid;
         count += tmp;
      }
      if(count < F)
         right = mid;
      else
         left = mid;
   }
   printf("%0.4lf\n" , right);
}

int main(){
   scanf("%d" , &t); 
   while(t--){
      scanf("%d%d" , &N , &F);
      sum = 0;
      F++;
      for(int i = 0 ; i < N ; i++){
          scanf("%lf" , &r[i]);
          sum += r[i]*r[i];
      }
      solve();
   }
   return 0;
}

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

const double eps = 1e-6;
const double PI = 3.1415926535898;
const int MAXN = 10010;
int n , numFriend;
struct pie{
    double r;
    double size;
};
pie p[MAXN];

bool judge(double s){
     int cnt = 0;
     for(int i = 0 ; i < n ; i++)
         cnt += p[i].size/s;
     return cnt >= numFriend+1 ? true : false;
}

double solve(double Min , double Max){
     double left , right , mid;
     left = Min , right = Max;
     while(right-left > eps){
         double mid = left+(right-left)/2;
         if(judge(mid))
            left = mid;
         else
            right = mid;
     }
     return left;
}

int main(){
    int Case , pos;
    double Min , Max;
    scanf("%d" , &Case);
    while(Case--){
        scanf("%d%d" , &n , &numFriend);
        Max = 0.0 , Min = 1>>30;
        for(int i = 0 ; i < n ; i++){
            scanf("%lf" , &p[i].r);
            p[i].size = PI*p[i].r*p[i].r;
            Max = max(Max , p[i].size);
            Min = min(Min , p[i].size);
        }
        printf("%.4lf\n" , solve(Min , Max)); 
    }
    return 0;
}