Divide and conquer:Cable Master(POJ 1064)

 1 #include <iostream>
 2 #include <algorithm>
 3 #include <functional>
 4 #include <math.h>
 5 #define MAX 1000000
 6 
 7 using namespace std;
 8 
 9 static double s_set[10010];
10 
11 bool C(const double, const int, const int);
12 
13 int main(void)
14 {
15     int string_sum, cnt;
16     double lb, rb, mid;
17 
18     while (~scanf("%d%d", &string_sum, &cnt))
19     {
20         for (int i = 0; i < string_sum; i++)
21             scanf("%lf", &s_set[i]);
22         lb = 0; rb = MAX;
23 
24         for (int i = 0; i < 50; i++)//50的精度已经足够了
25         {
26             mid = (lb + rb) / 2;
27             if (C(mid, string_sum, cnt))
28                 lb = mid;
29             else
30                 rb = mid;
31         }
32         printf("%.2f\n", floor(mid * 100) / 100);//防止四舍五入
33     }
34 
35     return 0;
36 }
37 
38 bool C(const double cut, const int string_sum, const int K)
39 {
40     int tmp_sum = 0;
41     for (int i = 0; i < string_sum; i++)
42         tmp_sum += (int)(s_set[i] / cut);
43 
44     return tmp_sum >= K;
45 }