P4782 运输木材（基础）

解题思路

第一步，读懂题目。 木材厂有 n 根大木头，每根长 a_i。要把它们切成长度都相等的小木头，卡车至少装 m 根才发车。问小木头最长能切多长，切不出来就输出 0。

第二步，把问题倒过来。 和分巧克力一样，直接求最大长度不好算，我们反过来问：如果小木头长度是 x，一共能切出多少根？每根大木头 a_i 能切出 a_i 除以 x 根（向下取整），把 n 根的答案加起来就是总数。

第三步，判断可行性。 如果总数不少于 m，说明长度 x 可行，可以试试更长的；否则不行，要试试更短的。长度越大，切出的根数越少，所以“长度 x 可行”是单调的，可以用二分答案。

第四步，处理切不出来的情况。 如果所有大木头的总长度加起来都不到 m，那么连 1 厘米长的小木头都凑不出 m 根，肯定切不出来，直接输出 0。比如只有一根 5 厘米的木头却要 6 根，肯定不行。

第五步，注意数据类型。 计算总数时要用 long long，因为 n 和 a_i 可能很大，总数可能超过 int 能表示的范围，用 long long 才能装得下。

第六步，理解二分的循环过程。 我们维护两个边界 left 和 right，答案就在 left 和 right 之间。每次取中间值 mid = (left+right)/2，计算一下小木头长度为 mid 时能切出的总数。如果总数不少于 m，说明 mid 可行，答案至少是 mid，于是把 left 改成 mid+1，去右边找更大的长度；否则说明 mid 太大，把 right 改成 mid-1，去左边找。一直循环到 left 超过 right，最后一次记下的 answer 就是最大长度。

第七步，举一个例子。 四根木头分别是 18、6、11、7，要 m=7 根。长度取 5 时：18/5 + 6/5 + 11/5 + 7/5 = 3+1+2+1 = 7 根，可行；长度取 6 时：3+1+1+1 = 6 根，不够。所以答案是 5。

参考代码

// 运输木材：二分答案，判断长度 x 时能切出多少根小木头，找出能切出至少 m 根的最大长度
#include <iostream>
using namespace std;

int logLen[100005];

int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    int maxLog = 0;
    long long sumLog = 0;
    for (int i = 0; i < n; i++) {
        scanf("%d", &logLen[i]);
        if (logLen[i] > maxLog) maxLog = logLen[i];
        sumLog += logLen[i];
    }
    // 如果所有木头总长度加起来都不够 m，说明连 1 长度的也切不出 m 根，输出 0
    if (sumLog < m) {
        printf("0\n");
        return 0;
    }
    int left = 1, right = maxLog, answer = 1;
    while (left <= right) {
        int mid = (left + right) / 2;
        long long total = 0;
        for (int i = 0; i < n; i++) {
            // 每根长 logLen[i] 的木头能切出 logLen[i]/mid 根小木头
            total += logLen[i] / mid;
        }
        if (total >= m) {
            answer = mid;
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    printf("%d\n", answer);
    return 0;
}

复杂度分析

二分答案做 O(log maxLog) 轮，每轮遍历 n 根木头计算总数，是 O(n)。总时间复杂度 O(n log maxLog)。空间上只需要存 n 个长度的数组，是 O(n)。