3560. 寻找最小原木运输成本

Easy

题目描述

给你整数 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 <= 10^5
• 1 <= n, m <= 2 * k
• 输入保证总是可以运输原木。

提示：

• 如果两根原木的长度都小于 k，成本为零。
• 如果两根原木的长度都大于 k，我们能运输原木吗？
• 否则，选择长度较大的原木，将其切割成长度为 len1 和 len2 的两段，使得 len1 + len2 等于原始长度。
• 为了最小化成本 len1 * len2，选择 len1 和 len2 尽可能相差较大（例如 1 和 length-1）。

解题思路

这道题需要分情况讨论来找到最优的切割策略。

核心思路：

1. 如果两根原木长度都不超过 k，无需切割，成本为 0
2. 如果两根原木长度都超过 k，这种情况不可能存在（根据约束条件）
3. 如果只有一根原木长度超过 k，需要将其切割

切割策略分析： 当需要切割长度为 x 的原木时，设切割后两段长度为 a 和 b，其中 a + b = x，成本为 a * b。

为了最小化 a * b，在 a + b = x 固定的条件下，当 |a - b| 最大时，a * b 最小。因此最优切割方案是：

• 一段长度为 1，另一段长度为 x - 1
• 成本为 1 * (x - 1) = x - 1

算法步骤：

1. 检查两根原木是否都不超过 k，如果是则返回 0
2. 找出长度超过 k 的原木（最多一根）
3. 将其切割成长度为 1 和 x-1 的两段
4. 返回切割成本 x - 1

代码实现

class Solution {
public:
    long long minCuttingCost(int n, int m, int k) {
        if (n <= k && m <= k) {
            return 0;
        }
        
        if (n > k) {
            return n - 1;
        } else {
            return m - 1;
        }
    }
};

class Solution:
    def minCuttingCost(self, n: int, m: int, k: int) -> int:
        if n <= k and m <= k:
            return 0
        
        if n > k:
            return n - 1
        else:
            return m - 1

public class Solution {
    public long MinCuttingCost(int n, int m, int k) {
        if (n <= k && m <= k) {
            return 0;
        }
        
        if (n > k) {
            return n - 1;
        } else {
            return m - 1;
        }
    }
}

var minCuttingCost = function(n, m, k) {
    if (n <= k && m <= k) {
        return 0;
    }
    
    if (n > k) {
        return n - 1;
    } else {
        return m - 1;
    }
};

复杂度分析