题目描述
有一个 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
的蛋糕块的 最小 总开销。
样例
输入:m = 3, n = 2, horizontalCut = [1,3], verticalCut = [5]
输出:13
解释:
沿着垂直线 0 切开蛋糕,开销为 5 。
沿着水平线 0 切开 3 x 1 的蛋糕块,开销为 1 。
沿着水平线 0 切开 3 x 1 的蛋糕块,开销为 1 。
沿着水平线 1 切开 2 x 1 的蛋糕块,开销为 3 。
沿着水平线 1 切开 2 x 1 的蛋糕块,开销为 3 。
总开销为 5 + 1 + 1 + 3 + 3 = 13 。
输入:m = 2, n = 2, horizontalCut = [7], verticalCut = [4]
输出:15
解释:
沿着水平线 0 切开蛋糕,开销为 7 。
沿着垂直线 0 切开 1 x 2 的蛋糕块,开销为 4 。
沿着垂直线 0 切开 1 x 2 的蛋糕块,开销为 4 。
总开销为 7 + 4 + 4 = 15 。
限制
1 <= m, n <= 10^5
horizontalCut.length == m - 1
verticalCut.length == n - 1
1 <= horizontalCut[i], verticalCut[i] <= 10^3
算法
(贪心) $O(m \log m + n \log n)$
- 注意到,每条水平线和垂直线,最终都要全部切完。
- 每次切割水平线时,都需要额外付出这条线的代价乘之前切割的垂直线的个数。每次切割垂直线时同理。
- 对于水平线或者垂直线内部的切割顺序,在最优情况下,一定是先切割代价大的,然后再切割代价小的。否则,内部交换两个切割顺序会使答案变优。
- 同理,对于按代价倒序排好的水平线和垂直线,仍然是优先切割代价大的,否则交换两个切割顺序也会使答案变优。
- 所以,按照代价倒序进行切割,遍历的途中计算出前面已经切割的水平线或垂直线的个数计算答案。
时间复杂度
- 排序的时间复杂度为 $O(m \log m + n \log n)$。
- 排序后,仅需要遍历两个数组一次。
- 故总时间复杂度为 $O(m \log m + n \log n)$。
空间复杂度
- 需要 $O(\log m + \log n)$ 的额外空间存储排序的系统栈。
C++ 代码
#define LL long long
class Solution {
public:
LL minimumCost(
int m, int n,
vector<int>& horizontalCut, vector<int>& verticalCut
) {
sort(horizontalCut.begin(), horizontalCut.end());
sort(verticalCut.begin(), verticalCut.end());
int i = m - 2, j = n - 2;
LL ans = 0;
while (i >= 0 || j >= 0) {
if (j == -1 || (i >= 0 && horizontalCut[i] > verticalCut[j])) {
ans += (LL)(horizontalCut[i]) * (n - j - 1);
i--;
} else {
ans += (LL)(verticalCut[j]) * (m - i - 1);
j--;
}
}
return ans;
}
};