嗯...

 

题目链接：

 

其实这是一道很好想的二分答案的一道题...

 

二分的区间就是1~max_l，从1开始是因为所有小于1的都需要按0计算，没必要讨论了...

每次二分出来的答案看它能否把电缆切成大于等于k块，如果可以，我们不能保证它是最优的答案，所以要向更大的地方二分；如果现在都不可以，我们必须向更小的地方二分，才有可能可以。

 

这道题注意二分一般在整数中二分，所以我们先把它们都乘100，如果要求精度更高，则乘的数更大，然后再整数二分，最后输出的时候再除回去即可...注意初始化...

 

AC代码：

1 #include
      
        2 #include
       
         3  4 using namespace std; 5  6 int ans, n, k, a[10004], max_l; 7  8 inline void er_fen(){ 9     int l = 1, r = max_l;10     while(l <= r){11         int cnt = 0;12         int mid = (l + r) >> 1;13         for(int i = 1; i <= n; i++){14             cnt += a[i] / mid;15         }16         if(cnt >= k){17             ans = max(ans, mid);18             l = mid + 1;19         }20         else r = mid - 1;21     }22 }23 24 int main(){25     while(scanf("%d%d", &n, &k) != EOF){26         max_l = -1, ans = 0;27         for(int i = 1; i <= n; i++){28             double len;29             scanf("%lf", &len);30             a[i] = len * 100;31             max_l = max(max_l, a[i]);32         }33         er_fen();34         printf("%.2f\n", (double) ans / 100.0);35     }36     return 0;37 }