目标
有一个 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
解释：
沿着垂直线 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 。示例 2：
输入：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
思路
有一块 m x n 的蛋糕，horizontalCut[i] 表示水平切第 i 行的开销，verticalCut[i] 表示垂直切第 i 列的开销。求将蛋糕切成 1 x 1 小块的最小代价。
与 切蛋糕的最小总开销I 相比数据范围扩大了，返回值是 long 型。
代码
/**
* @date 2024-12-26 16:38
*/
public class MinimumCost3219 {
public long minimumCost(int m, int n, int[] horizontalCut, int[] verticalCut) {
int horizontalPart = m;
int verticalPart = n;
Arrays.sort(horizontalCut);
Arrays.sort(verticalCut);
int h = 0;
int v = 0;
long res = 0;
while (h < m - 1 || v < n - 1) {
int hcost = h >= m - 1 ? Integer.MAX_VALUE : horizontalCut[h];
int vcost = v >= n - 1 ? Integer.MAX_VALUE : verticalCut[v];
if (hcost < vcost) {
res += verticalPart * hcost;
horizontalPart--;
h++;
} else {
res += horizontalPart * vcost;
verticalPart--;
v++;
}
}
return res;
}
}
性能
