P4767 造海船（基础）

解题思路

郑和下西洋要造大船，手上有 n 根原木，要把它们切成 k 段"长度都相等"的小段木头，每段长度是 l，多余的部分可以浪费掉。工匠想让小段木头尽可能长，也就是让 l 尽量大，但要保证能切出至少 k 段。如果连长度 1 的小段都切不出 k 段，就输出 0。这道题用"二分答案"来做，分成几步：

1. 第一步，认识二分答案。 要猜的答案 l 是一个数，它的范围很明显：最短是 1，最长不会超过最长那根原木的长度 maxLen。在这个范围里，l 越大能切出的段数越少，l 越小段数越多——存在单调性，所以可以二分快速找到最大的可行 l。打个比方：同样的木头，切成 1 段肯定行，切成 2 段可能行，切成几千段可能就不行了；段数随着每段长度变小而变多，方向固定、不会反复无常，这就是单调性。从 1 到 1 亿一个一个试太慢，二分每次砍掉一半，几下就能锁定答案。

2. 第二步，想清楚怎么判断一个候选长度。 判断候选长度 mid 是否可行很简单：对于每一根原木，长度 logs[i] 能切出 logs[i] / mid 段（整除），把所有原木的段数加起来得到 total，如果 ≥ k，说明 mid 可行，还能把 l 再加大；如果 < k，说明 mid 太大、切不够 k 段，就得把 l 缩小。

3. 第三步，二分到最后记录答案。 每次 mid 可行就把答案 answer 记下来，再把下界 low 抬高；不可行就把上界 high 压低。二分结束时 answer 就是最大可行长度。

4. 第四步，用样例验证。 三根原木 232、124、456，要切 7 段。如果每段 114：232/114=2、124/114=1、456/114=4，一共 2+1+4=7 段，刚好够；如果每段 115：2+1+3=6 段，不够。所以答案是 114。

5. 第五步，注意防溢出的细节。 k 最大能到 100000000（1 亿），每根原木最长 1 亿，所以统计段数的 total 要用 long long，防止多根原木的段数加起来溢出。

6. 第六步，想想输出 0 的边界。 如果连长度 1 都切不出 k 段，说明原木实在太少，二分过程中每次检查 total 都 < k，answer 会一直保持初始值 0，正好符合题目要求输出 0，不用额外特判。

参考代码

// 造海船：把n根原木切成k段等长小段，二分答案求小段最大长度
#include <iostream>
int main() {
    long long n, k;
    std::cin >> n >> k;
    long long logs[100005] = {0}; // logs[i] 存第 i 根原木的长度
    long long maxLen = 0; // 记录最长的原木，作为二分上界
    for (int i = 1; i <= n; ++i) {
        std::cin >> logs[i];
        if (logs[i] > maxLen) maxLen = logs[i];
    }
    long long low = 1, high = maxLen, answer = 0;
    while (low <= high) {
        long long mid = (low + high) / 2; // 假设每段长度是 mid
        long long total = 0;              // 统计能切出多少段
        for (int i = 1; i <= n; ++i) total += logs[i] / mid;
        if (total >= k) { // 段数够多，可以试试更长的小段
            answer = mid;
            low = mid + 1;
        } else {          // 段数不够，说明小段太长，需要缩短
            high = mid - 1;
        }
    }
    std::cout << answer << '\n';
    return 0;
}

复杂度分析

二分答案的区间是 [1, maxLen]，maxLen 最大 100000000，log2(100000000) 约 27 次；每次判断都要遍历 n 根原木，n 最大 100000，所以总时间复杂度是 O(n log maxLen)，大约 270 万次操作。空间复杂度 O(n)。如果从 1 到 maxLen 一个一个试 l，最坏要试 1 亿次，每次都遍历 10 万根原木，会超时；二分把试的次数压缩到了 27 次左右，这就是二分的威力。