class Solution {
public:
long long minimumCost(int m, int n, vector<int>& horizontalCut, vector<int>& verticalCut) {
}
};
100367. 切蛋糕的最小总开销 II
有一个 m x n
大小的矩形蛋糕,需要切成 1 x 1
的小块。
给你整数 m
,n
和两个数组:
horizontalCut
的大小为 m - 1
,其中 horizontalCut[i]
表示沿着水平线 i
切蛋糕的开销。verticalCut
的大小为 n - 1
,其中 verticalCut[j]
表示沿着垂直线 j
切蛋糕的开销。一次操作中,你可以选择任意不是 1 x 1
大小的矩形蛋糕并执行以下操作之一:
i
切开蛋糕,开销为 horizontalCut[i]
。j
切开蛋糕,开销为 verticalCut[j]
。每次操作后,这块蛋糕都被切成两个独立的小蛋糕。
每次操作的开销都为最开始对应切割线的开销,并且不会改变。
请你返回将蛋糕全部切成 1 x 1
的蛋糕块的 最小 总开销。
示例 1:
输入:m = 3, n = 2, horizontalCut = [1,3], verticalCut = [5]
输出:13
解释:
3 x 1
的蛋糕块,开销为 1 。3 x 1
的蛋糕块,开销为 1 。2 x 1
的蛋糕块,开销为 3 。2 x 1
的蛋糕块,开销为 3 。总开销为 5 + 1 + 1 + 3 + 3 = 13
。
示例 2:
输入:m = 2, n = 2, horizontalCut = [7], verticalCut = [4]
输出:15
解释:
1 x 2
的蛋糕块,开销为 4 。1 x 2
的蛋糕块,开销为 4 。总开销为 7 + 4 + 4 = 15
。
提示:
1 <= m, n <= 105
horizontalCut.length == m - 1
verticalCut.length == n - 1
1 <= horizontalCut[i], verticalCut[i] <= 103
原站题解
golang 解法, 执行用时: 353 ms, 内存消耗: 8.5 MB, 提交时间: 2024-07-15 10:09:52
func minimumCost1(m, n int, horizontalCut, verticalCut []int) int64 { slices.SortFunc(horizontalCut, func(a, b int) int { return b - a }) slices.SortFunc(verticalCut, func(a, b int) int { return b - a }) ans := 0 cntH, cntV := 1, 1 i, j := 0, 0 for i < m-1 || j < n-1 { if j == n-1 || i < m-1 && horizontalCut[i] > verticalCut[j] { ans += horizontalCut[i] * cntH // 横切 i++ cntV++ // 需要竖切的蛋糕块增加 } else { ans += verticalCut[j] * cntV // 竖切 j++ cntH++ // 需要横切的蛋糕块增加 } } return int64(ans) } // 优化 func minimumCost(m, n int, horizontalCut, verticalCut []int) int64 { slices.SortFunc(horizontalCut, func(a, b int) int { return b - a }) slices.SortFunc(verticalCut, func(a, b int) int { return b - a }) ans := 0 i, j := 0, 0 for i < m-1 || j < n-1 { if j == n-1 || i < m-1 && horizontalCut[i] > verticalCut[j] { ans += horizontalCut[i] * (j + 1) // 横切 i++ } else { ans += verticalCut[j] * (i + 1) // 竖切 j++ } } return int64(ans) }
java 解法, 执行用时: 91 ms, 内存消耗: 61.5 MB, 提交时间: 2024-07-15 10:07:54
class Solution { public long minimumCost1(int m, int n, int[] horizontalCut, int[] verticalCut) { Arrays.sort(horizontalCut); // 下面倒序遍历 Arrays.sort(verticalCut); long ans = 0; int i = m - 2; int j = n - 2; int cntH = 1; int cntV = 1; while (i >= 0 || j >= 0) { if (j < 0 || i >= 0 && horizontalCut[i] > verticalCut[j]) { ans += horizontalCut[i--] * cntH; // 横切 cntV++; // 需要竖切的蛋糕块增加 } else { ans += verticalCut[j--] * cntV; // 竖切 cntH++; // 需要横切的蛋糕块增加 } } return ans; } // 优化 public long minimumCost(int m, int n, int[] horizontalCut, int[] verticalCut) { Arrays.sort(horizontalCut); // 下面倒序遍历 Arrays.sort(verticalCut); long ans = 0; int i = m - 2; int j = n - 2; while (i >= 0 || j >= 0) { if (j < 0 || i >= 0 && horizontalCut[i] > verticalCut[j]) { ans += horizontalCut[i--] * (n - 1 - j); // 横切 } else { ans += verticalCut[j--] * (m - 1 - i); // 竖切 } } return ans; } }
cpp 解法, 执行用时: 417 ms, 内存消耗: 227.2 MB, 提交时间: 2024-07-15 10:06:21
class Solution { public: long long minimumCost1(int m, int n, vector<int>& horizontalCut, vector<int>& verticalCut) { ranges::sort(horizontalCut, greater<>()); ranges::sort(verticalCut, greater<>()); long long ans = 0; int cnt_h = 1, cnt_v = 1; int i = 0, j = 0; while (i < m - 1 || j < n - 1) { if (j == n - 1 || i < m - 1 && horizontalCut[i] > verticalCut[j]) { ans += horizontalCut[i++] * cnt_h; // 横切 cnt_v++; // 需要竖切的蛋糕块增加 } else { ans += verticalCut[j++] * cnt_v; // 竖切 cnt_h++; // 需要横切的蛋糕块增加 } } return ans; } // 优化 long long minimumCost(int m, int n, vector<int>& horizontalCut, vector<int>& verticalCut) { ranges::sort(horizontalCut, greater<>()); ranges::sort(verticalCut, greater<>()); long long ans = 0; int i = 0, j = 0; while (i < m - 1 || j < n - 1) { if (j == n - 1 || i < m - 1 && horizontalCut[i] > verticalCut[j]) { ans += horizontalCut[i++] * (j + 1); // 横切 } else { ans += verticalCut[j++] * (i + 1); // 竖切 } } return ans; } };
python3 解法, 执行用时: 578 ms, 内存消耗: 28.6 MB, 提交时间: 2024-07-15 10:05:18
class Solution: # 谁开销大,先切谁,留到后面只会开销更大 def minimumCost1(self, m: int, n: int, horizontalCut: List[int], verticalCut: List[int]) -> int: horizontalCut.sort(reverse=True) verticalCut.sort(reverse=True) ans = i = j = 0 cnt_h = cnt_v = 1 while i < m - 1 or j < n - 1: if j == n - 1 or i < m - 1 and horizontalCut[i] > verticalCut[j]: ans += horizontalCut[i] * cnt_h # 横切 i += 1 cnt_v += 1 # 需要竖切的蛋糕块增加 else: ans += verticalCut[j] * cnt_v # 竖切 j += 1 cnt_h += 1 # 需要横切的蛋糕块增加 return ans # 优化 def minimumCost(self, m: int, n: int, horizontalCut: List[int], verticalCut: List[int]) -> int: horizontalCut.sort(reverse=True) verticalCut.sort(reverse=True) ans = i = j = 0 while i < m - 1 or j < n - 1: if j == n - 1 or i < m - 1 and horizontalCut[i] > verticalCut[j]: ans += horizontalCut[i] * (j + 1) # 横切 i += 1 else: ans += verticalCut[j] * (i + 1) # 竖切 j += 1 return ans