P4776 新校区布网（2）（提高）

这道题和"新校区布网"是同一个问题，区别是这次网线的长度都是整数米，问能切出 K 条等长网线的最长长度是多少米。

解题思路

1. 输入都是整数。 每条网线的长度是整数米（1 到 10^8），答案也是整数米，不需要处理小数。

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

3. 二分的写法。 low = 0，high = 最长的网线。每次取 mid = (low + high + 1) / 2 检查总数。够 K 条就 low = mid，试试更长的；不够就 high = mid - 1。

4. 切不够的情况。 如果所有网线加起来都不够 K 米（比如只有 1 米长却要切 2 条），那连 1 米都切不够，二分结束时 low 是 0，输出 0。

5. 注意用 long long。 N 最大 10^5，每条网线最长 10^8 米，所有长度加起来可能到 10^13，超出 int 的范围，一定要用 long long 存，否则会溢出出错。

6. 具体例子。 三条网线 456、567、678 米，要切 8 条。检查 189 米：456/189=2、567/189=3、678/189=3，正好 8 条，可行；检查 190 米只有 7 条，不够。所以答案是 189。

参考代码

// 新校区布网（2）：网线长度是整数，用二分答案求出能切出K条网线的最长长度
#include <cstdio>
using namespace std;
long long wireLength[100005]; // 每条网线的长度（单位：米）

int main(){
    int n, k;
    scanf("%d%d", &n, &k);
    long long maxLength = 0;
    for(int i = 0; i < n; i++){
        scanf("%lld", &wireLength[i]);
        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
    printf("%lld\n", low);
    return 0;
}

复杂度分析

二分答案的范围是 [0, 10^8]，约 27 次检查；每次检查要扫一遍 N 条网线（N ≤ 10^5），所以时间复杂度是 O(N log maxLen)，大约 270 万次运算，非常快。空间上用一个数组存每条网线的长度，空间复杂度是 O(N)。