Skip to content

3560. Find Minimum Log Transportation Cost

Description

You are given integers n, m, and k.

There are two logs of lengths n and m units, which need to be transported in three trucks where each truck can carry one log with length at most k units.

You may cut the logs into smaller pieces, where the cost of cutting a log of length x into logs of length len1 and len2 is cost = len1 * len2 such that len1 + len2 = x.

Return the minimum total cost to distribute the logs onto the trucks. If the logs don't need to be cut, the total cost is 0.

 

Example 1:

Input: n = 6, m = 5, k = 5

Output: 5

Explanation:

Cut the log with length 6 into logs with length 1 and 5, at a cost equal to 1 * 5 == 5. Now the three logs of length 1, 5, and 5 can fit in one truck each.

Example 2:

Input: n = 4, m = 4, k = 6

Output: 0

Explanation:

The two logs can fit in the trucks already, hence we don't need to cut the logs.

 

Constraints:

  • 2 <= k <= 105
  • 1 <= n, m <= 2 * k
  • The input is generated such that it is always possible to transport the logs.

Solutions

Solution 1: Mathematics

If the lengths of both logs do not exceed the truck's maximum load \(k\), then no cutting is needed, and we simply return \(0\).

Otherwise, it means that only one log has a length greater than \(k\), and we need to cut it into two pieces. Let the longer log have length \(x\), then the cutting cost is \(k \times (x - k)\).

The time complexity is \(O(1)\), and the space complexity is \(O(1)\).

1
2
3
4
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)

1
2
3
4
5
6
class Solution {
    public long minCuttingCost(int n, int m, int k) {
        int x = Math.max(n, m);
        return x <= k ? 0 : 1L * k * (x - k);
    }
}

1
2
3
4
5
6
7
class Solution {
public:
    long long minCuttingCost(int n, int m, int k) {
        int x = max(n, m);
        return x <= k ? 0 : 1LL * k * (x - k);
    }
};

1
2
3
4
5
6
7
func minCuttingCost(n int, m int, k int) int64 {
    x := max(n, m)
    if x <= k {
        return 0
    }
    return int64(k * (x - k))
}

1
2
3
4
function minCuttingCost(n: number, m: number, k: number): number {
    const x = Math.max(n, m);
    return x <= k ? 0 : k * (x - k);
}

Comments