首页 > 代码库 > HDU 1969

HDU 1969

2024-07-13 02:56:36   224人阅读

陶叔说的比较灵活的二分

开始的时候并没有弄清楚这是什么情况

再想到二分

 

那么就是把最大Pie的面积作为上界，下界为0

就解决了

 1 #include <iostream> 2 #include <cmath> 3 #include <algorithm> 4 #include <stdio.h> 5 using namespace std; 6  7  8 int main() 9 {10     int T;11     cin>>T;12     for(int test = 0;test<T;test++)13     {14     int N,F;15     cin>>N>>F;16     F+=1;17 18     int* Radius = new int[N];19     double* Pie = new double[N];20     for(int i =0;i<N;i++)21     {22     cin>>Radius[i];23     Pie[i] = Radius[i]*Radius[i]*acos(-1.0);24     }25 26     sort(Pie,Pie+N);27 28     double high = Pie[N-1];29     double low = 0;30 31     while(high-low>1e-5)32     {33         double mid = (high + low)/2.0;34         bool isEnough = false;35         int num = 0;36         for(int j =0; j<N ; j++)37         {38             num+=(int)(Pie[j]/mid);39        }40          isEnough = (num>=F);41         if(isEnough)42         {43             low = mid;44         }else45         {46         high = mid;47         }48     }49     printf("%.4lf\n",(high+low)/2.0);50     }51 52     return 0;53 }


联系
我们