Welcome to Subscribe On Youtube

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)$.

  • 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);
    }
}

  • 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);
    }
};

  • 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)


  • func minCuttingCost(n int, m int, k int) int64 {
	x := max(n, m)
	if x <= k {
		return 0
	}
	return int64(k * (x - k))
}

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

All Problems

All Solutions