LeetCode 题解工作台
木材运输的最小成本
给你三个整数 n 、 m 和 k 。 有两根长度分别为 n 和 m 单位的木材，需要通过三辆卡车运输。每辆卡车最多只能装载一根长度 不超过 k 单位的木材。 你可以将木材切成更小的段，其中将长度为 x 的木材切割成长度为 len1 和 len2 的段的成本为 cost = len1 * len2 ，…
1
题型
5
代码语言
3
相关题
当前训练重点
简单 · 数学·driven
答案摘要
如果两根木材的长度都不超过卡车的最大载重 ，则不需要切割，直接返回 。 否则，说明只有一个木材的长度超过了 ，我们需要将其切割成两段。设较长的木材长度为 ，则切割成本为 $k \times (x - k)$。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数学·driven 题型思路
题目描述
给你三个整数 n、m 和 k。
有两根长度分别为 n 和 m 单位的木材，需要通过三辆卡车运输。每辆卡车最多只能装载一根长度 不超过 k 单位的木材。
你可以将木材切成更小的段，其中将长度为 x 的木材切割成长度为 len1 和 len2 的段的成本为 cost = len1 * len2，并且满足 len1 + len2 = x。
返回将木材分配到卡车上的 最小总成本 。如果木材不需要切割，总成本为 0。
示例 1：
输入： n = 6, m = 5, k = 5
输出： 5
解释：
将长度为 6 的木材切割成长度为 1 和 5 的两段，成本为 1 * 5 == 5。现在三段长度分别为 1、5 和 5 的木材可以分别装载到每辆卡车。
示例 2：
输入： n = 4, m = 4, k = 6
输出： 0
解释：
两根木材已经可以直接装载到卡车上，因此不需要切割。
提示：
2 <= k <= 1051 <= n, m <= 2 * k- 输入数据保证木材总存在能被运输的方案。
解题思路
方法一：数学
如果两根木材的长度都不超过卡车的最大载重 ，则不需要切割，直接返回 。
否则，说明只有一个木材的长度超过了 ，我们需要将其切割成两段。设较长的木材长度为 ，则切割成本为 。
时间复杂度 ，空间复杂度 。
class Solution:
def minCuttingCost(self, n: int, m: int, k: int) -> int:
x = max(n, m)
return 0 if x <= k else k * (x - k)
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | and space complexity depend on the number of valid cut points considered per log. Evaluating all splits is linear in the log length, while the total cost calculation adds constant overhead. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Look for a direct check if logs fit without cutting.
- question_mark
Evaluate the efficiency of different cut strategies for minimal cost.
- question_mark
Expect reasoning about multiplication cost trade-offs between different cut points.
常见陷阱
外企场景- error
Assuming each log must be cut even if both are within truck capacity.
- error
Choosing cut points without checking if resulting pieces exceed k.
- error
Forgetting that the cost is the product of split lengths, not the sum.
进阶变体
外企场景- arrow_right_alt
More than two logs with different truck capacities.
- arrow_right_alt
Variable cutting costs such as sum or squared length instead of product.
- arrow_right_alt
Dynamic truck assignment where each truck can carry multiple small pieces.