P4774 新校区布网（提高）

学校需要把库存的网线切成 K 条等长的网线，要求长度越长越好，但必须切够 K 条。每条网线的长度精确到厘米。我们需要找出最长能切够 K 条的长度。

解题思路

1. 把长度都换成厘米。 输入的长度单位是"米"并保留两位小数，比如 8.02。先把每条网线乘以 100 变成厘米的整数，8.02 就变成 802 厘米，这样之后全部用整数计算，就不会有小数的误差了。

2. 二分答案。 答案一定是某个整厘米数。假设答案是 len 厘米，那么第 i 条网线能切出 wireLength[i] / len 条，把 N 条加起来如果大于等于 K，就说明这个长度可行。长度越大越难切够，所以可以二分在 [0, 最长网线] 里找最大的可行长度。

3. 二分的写法。 low = 0，high = 最长网线的厘米数。每次取 mid = (low + high + 1) / 2（这样取中间偏上，保证最后 low 就是最大的可行解）。如果按 mid 能切够 K 条，就说明还能更长，low = mid；否则说明太长切不够，high = mid - 1。

4. 切不够的情况。 如果连 1 厘米长的网线都凑不齐 K 条，二分结束时 low 就是 0，输出 "0.00"。

5. 输出格式。 把答案厘米转回米：low / 100 是整数部分，low % 100 是小数部分，用 %lld.%02lld 输出两位小数。比如答案是 200 厘米，就输出 2.00。

参考代码

// 新校区布网：把所有网线长度换算成厘米，用二分答案求出能切出K条网线的最长长度
#include <cstdio>
using namespace std;
long long wireLength[10005]; // 每条网线的长度（单位：厘米）

int main(){
    int n, k;
    scanf("%d%d", &n, &k);
    long long maxLength = 0;
    for(int i = 0; i < n; i++){
        double x;
        scanf("%lf", &x);
        wireLength[i] = (long long)(x * 100 + 0.5); // 米转厘米，四舍五入保证精度
        if(wireLength[i] > maxLength) maxLength = wireLength[i];
    }
    long long low = 0, high = maxLength;
    // 二分答案：找最大的长度，使得能切出至少k条网线
    while(low < high){
        long long mid = (low + high + 1) / 2;
        long long total = 0; // 按mid厘米长能切出的网线总数
        for(int i = 0; i < n; i++){
            total += wireLength[i] / mid;
        }
        if(total >= k){
            low = mid;       // 能切够k条，试试更长的
        } else {
            high = mid - 1;  // 切不够k条，只能选更短的
        }
    }
    // 把厘米转回米，保留两位小数；如果一条都切不出，low就是0，输出0.00
    printf("%lld.%02lld\n", low / 100, low % 100);
    return 0;
}

复杂度分析

二分答案在 [0, 10^7] 厘米之间进行，约 log2(10^7) ≈ 24 次；每次检查都要扫描 N 条网线（N ≤ 10000），所以总时间复杂度是 O(N log maxLen)，大约 24 万次运算，非常快。空间上用一个数组存每条网线的长度，空间复杂度是 O(N)。