LeetCode 补充题 7. 木头切割问题

2024-09-05 HGNULB 约 6 分钟

文章信息 7 个分类 1 个标签

分类

题目描述

✅ 补充题 7. 木头切割问题

题意分析

手上有若干根长度各异的木头，需要把它们裁成至少 k 段长度完全相同的小段，问这个统一的段长最大能取到多少。段长必须是正整数，裁剪时每根木头独立处理，裁剩下的零头直接丢弃，也允许某根木头一段都出不了。

题目问的是「最大的可行值」，而不是让我们构造出具体的切割方案。这个措辞是关键信号：只要能对任意一个候选段长快速回答「行不行」，就不必真的去规划怎么切。

边界上要留意两处。其一，木头总长可能凑不出 k 段，此时无解，按约定返回 0。其二，段长为 0 没有意义（会导致除零），所以候选值必须从 1 起步。另外木头根数和长度都可能很大，长度 / 段长 的累加结果有溢出到 32 位之外的风险。

解法：二分答案找最大可行长度

核心思路

对候选段长 len，能切出的段数为 sum(wood / len)。随着 len 增大，每一项都不会增大，因此判定函数

canCut(len) = 能否切出至少 k 段

呈现「一段可行、一段不可行」的单调性。题目要求最大的可行段长，所以可以在答案范围 [1, maxWood] 上二分，而不必逐个尝试。

闭区间二分维护：尚未排除的答案位于 [left, right]。若 mid 可行，记录它并向右找更大值；否则向左缩小。循环结束后记录的就是最后一个可行值。若所有正长度都不可行，答案保持 0。

解题步骤

扫描数组得到最长木头 maxWood，它是答案上界。

在 [1, maxWood] 内取中点 mid。

累加每根木头能切出的 wood / mid 段；达到 k 后即可提前返回可行。

可行时令 ans = mid、继续搜索右半区；不可行时搜索左半区。

区间为空后返回 ans。

例如 woods = [232, 124, 456]、k = 7：长度 114 能切出 $2 + 1 + 4 = 7$ 段，而长度 115 只能切出 $2 + 1 + 3 = 6$ 段，所以答案是 114。

代码实现

class Solution {
    public int woodCut(int[] woods, int k) {
        int right = 0;
        for (int wood : woods) {
            right = Math.max(right, wood);
        }

        int left = 1;
        int ans = 0;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (canCut(woods, k, mid)) {
                ans = mid;
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return ans;
    }

    private boolean canCut(int[] woods, int k, int len) {
        long count = 0;
        for (int wood : woods) {
            count += wood / len;
            if (count >= k) {
                return true;
            }
        }
        return false;
    }
}

func woodCut(woods []int, k int) int {
    right := 0
    for _, wood := range woods {
        if wood > right {
            right = wood
        }
    }

    left, ans := 1, 0
    for left <= right {
        mid := left + (right-left)/2
        if canCutWood(woods, k, mid) {
            ans = mid
            left = mid + 1
        } else {
            right = mid - 1
        }
    }
    return ans
}

func canCutWood(woods []int, k, length int) bool {
    var count int64
    for _, wood := range woods {
        count += int64(wood / length)
        if count >= int64(k) {
            return true
        }
    }
    return false
}

复杂度分析

时间复杂度：$O(n log M)$，其中 $n$ 是木头数量，$M$ 是最长木头；每轮判定扫描数组，值域被折半。

空间复杂度：$O(1)$。

关键点总结

二分答案依赖的是判定函数单调，不要求输入数组有序，也无需排序木头。

下界必须是 1，避免除零；上界取最长木头即可。

本题找「最大可行值」，可行时要向右搜索；若改成找「最小可行值」，移动方向与收尾答案都要相应调整。

整数除法正好表示零头丢弃，段数累加使用 64 位并在达到 k 时提前停止。

面试时应先给出 canCut 的单调性证明，再写二分模板；只说“看到最大值就二分”并不充分。

易错点总结

把 0 放入搜索区间：判定时会发生除零。

可行时向左收缩：会找到最小可行值，而不是最大段长。

判定写成 count > k：恰好能切出 k 段也应视为可行。

循环结束返回 left：它通常是第一个不可行值；本文直接维护 ans 避免混淆。

用总长度除以 k 当答案：不同木头的零头不能拼接，这个值只是上界，不一定可行。

相似题目

题目	难度	考察点
69. x 的平方根	简单	判定函数只是一次乘法，重点在溢出与取整方向
410. 分割数组的最大值	困难	判定改为贪心分段计数，求的是最小可行上限
644. 子数组最大平均数 II	困难	在实数域上二分，判定要靠减去均值后的前缀和技巧
668. 乘法表中第k小的数	困难	判定是逐行统计不超过某值的元素个数，属第 K 小型二分
719. 找出第 K 小的数对距离	困难	判定需先排序再用双指针数对，二分与滑窗结合
774. 最小化去加油站的最大距离	困难	答案是实数，需按精度控制迭代轮数而非整数收敛
875. 爱吃香蕉的珂珂	中等	判定同样是向上取整求和，但目标是最小可行速度，返回左界
878. 第 N 个神奇数字	困难	判定要用容斥与最小公倍数计数，还要对大数取模
1011. 在 D 天内送达包裹的能力	中等	包裹顺序不可打乱，判定是顺序贪心装载而非独立求和
1201. 丑数 III	中等	判定用三数容斥计数，需要处理最小公倍数溢出
1231. 分享巧克力	困难	只能沿原顺序切分且必须切满份数，判定是累加到阈值即断
1482. 制作 m 束花所需的最少天数	中等	在时间轴上二分，判定要求连续相邻的若干朵同时开放
1552. 两球之间的磁力	中等	二分最小间距的最大值，判定是排序后贪心放球
LCP 12. 小张刷题计划	中等	判定中允许免除单日最大项，需要边扫边维护当前段最大值
LCR 072. x 的平方根	简单	同为整数开方，可对照牛顿迭代与二分的收敛速度差异
LCR 073. 爱吃香蕉的狒狒	中等	与本题互为镜像：同样是除法计数，但求最小而非最大