poj2106，POJ 1064 Cable master (二分答案)

2023-10-06 阅读 25 评论 0

摘要：題目鏈接：http://poj.org/problem?id=1064 有n條繩子，長度分別是Li。問你要是從中切出m條長度相同的繩子，問你這m條繩子每條最長是多少。二分答案，尤其注意精度問題。我覺得關于浮點數的二分for循環比while循環更好一點。注意最后要用到floo

題目鏈接：http://poj.org/problem?id=1064

有n條繩子，長度分別是Li。問你要是從中切出m條長度相同的繩子，問你這m條繩子每條最長是多少。

二分答案，尤其注意精度問題。我覺得關于浮點數的二分for循環比while循環更好一點。注意最后要用到floor 保證最后答案不會四舍五入。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cmath>
 4 using namespace std;
 5 int n , m;
 6 double len[int(1e4 + 5)];
 7 
 8 bool check(double x) {
 9     int res = 0;
10     for(int i = 0 ; i < n ; ++i)
11         res += int(len[i] / x);
12     return res >= m;
13 }
14 
15 int main()
16 {
17     while(~scanf("%d %d" , &n , &m)) {
18         for(int i = 0 ; i < n ; ++i)
19             scanf("%lf" , len + i);
20         double l = 0 , r = 10000000.0;
21         for(int i = 0 ; i < 100 ; ++i) {
22             double mid = (l + r) / 2.0;
23             if(check(mid))
24                 l = mid;
25             else
26                 r = mid;
27         }
28         printf("%.2f\n" , floor(l * 100) / 100);
29     }
30 }