UVALive - 3635 - Pie（二分）-白红宇

UVALive - 3635 - Pie（二分）

阅读量：5234 次

发布时间：2019-06-14

本文共 1597 字，大约阅读时间需要 5 分钟。

题意：有F + 1（1 <= F <= 10000）个人分N（1 <= N <= 10000）个圆形派，每个人得到的派面积相同，且必须是一整块（不能够两个甚至多个派拼在一起），求每个人最多能得到多大面积的派。（误差最多到0.001）

因为答案是小数类型的，并且N高达10000，故不可暴力枚举。

可以二分枚举最大面积，然后检查是否切出来派的总个数大于等于F + 1。

（判相等时不可直接判相等，需要加精度控制）

#include
     
        #include
      
         #include
       
          #include
        
           #include
         
            #include
          
            #include
           
             #include
            
              #include
             
               #include
              
                #include
               
                 #include
                
                  #include
                  #include
                  
                    #include
                   
                     #include
                    
                      #include
                     
                       #define fin freopen("in.txt", "r", stdin) #define fout freopen("out.txt", "w", stdout) #define pr(x) cout << #x << " : " << x << " " #define prln(x) cout << #x << " : " << x << endl typedef long long ll; typedef unsigned long long llu; const int INT_INF = 0x3f3f3f3f; const int INT_M_INF = 0x7f7f7f7f; const ll LL_INF = 0x3f3f3f3f3f3f3f3f; const ll LL_M_INF = 0x7f7f7f7f7f7f7f7f; const double pi = acos(-1.0); const double EPS = 1e-6; const int dx[] = { 0, 0, -1, 1}; const int dy[] = {-1, 1, 0, 0}; const ll MOD = 1e9 + 7; const int MAXN = 100 + 10; const int MAXT = 10000 + 10; using namespace std; int T, n, f; double a[MAXT]; bool judge(double area){ int sum = 0; for(int i = 0; i < n; ++i) sum += int(a[i] / area); return sum >= f; } int main(){ scanf("%d", &T); while(T--){ scanf("%d%d", &n, &f); for(int i = 0; i < n; ++i){ scanf("%lf", a + i); a[i] = a[i] * a[i] * pi; } ++f; double l = 0.0, r = *max_element(a, a + n); while(l + EPS < r){ double mid = (l + r) / 2; if(judge(mid)) l = mid; else r = mid; } printf("%.4lf\n", l); } return 0; }

转载于:https://www.cnblogs.com/tyty-TianTengtt/p/5996061.html

你可能感兴趣的文章