LeetCode 3219. 切蛋糕的最小总开销 II — Java 实现
题目概述
给定一个 `m × n` 的矩形蛋糕，需要切成 `1 × 1` 的小块。`horizontalCut[i]` 表示沿水平线 `i` 切割的开销，`verticalCut[j]` 表示沿垂直线 `j` 切割的开销。每次切割可以将任意非 `1 × 1` 的蛋糕块切开。求最小总开销。
---
解题思路
贪心策略：优先切开销大的
关键观察：一条切割线被切到的次数，等于在该切割之前已经完成的垂直切割次数 + 1（如果是水平切割）或水平切割次数 + 1（如果是垂直切割）。
因此，开销大的切割线应该尽早切，这样它乘上的段数更少。这等价于：
- 将 `horizontalCut` 和 `verticalCut` 按降序排列
- 每次选择当前剩余开销最大的切割线
- 水平切割的开销要乘以当前的垂直段数，垂直切割的开销要乘以当前的水平段数
---
Java 代码实现
```java
import java.util.Arrays;
class Solution {
public long minimumCost(int m, int n, int[] horizontalCut, int[] verticalCut) {
// 按降序排列，优先处理开销大的切割线
Arrays.sort(horizontalCut);
Arrays.sort(verticalCut);
long ans = 0;
int i = m - 2, j = n - 2; // 从最大开销开始
int h = 1, v = 1; // h: 水平段数, v: 垂直段数
while (i >= 0 || j >= 0) {
if (j < 0 || (i >= 0 && horizontalCut[i] > verticalCut[j])) {
// 优先切水平线
ans += (long) horizontalCut[i--] * v; // 乘以当前垂直段数
h++; // 水平段数 + 1
} else {
// 优先切垂直线
ans += (long) verticalCut[j--] * h; // 乘以当前水平段数
v++; // 垂直段数 + 1
}
}
return ans;
}
}
```
---
关键点说明
要点 说明
降序排序 `Arrays.sort()` 默认升序，所以从数组末尾开始遍历（`i = m-2`, `j = n-2`）
段数含义 `h` 表示当前水平方向上有多少段蛋糕块，`v` 表示垂直方向上有多少段
乘法逻辑 水平切割一次，会影响所有垂直段，所以乘以 `v`；垂直切割同理乘以 `h`
long 类型 结果可能很大，需要用 `long` 避免溢出
---
示例验证
示例 1：`m = 3, n = 2, horizontalCut = [1,3], verticalCut = [5]`
- 排序后：`horizontalCut = [1,3]`, `verticalCut = [5]`
- 初始：`h=1, v=1`, `i=1, j=0`
- 第1轮：`horizontalCut[1]=3 > verticalCut[0]=5`? 否 → 切垂直线 `5`，`ans += 5*1 = 5`，`v=2`, `j=-1`
- 第2轮：`j<0` → 切水平线 `3`，`ans += 3*2 = 6`，`h=2`, `i=0`
- 第3轮：切水平线 `1`，`ans += 1*2 = 2`，`h=3`, `i=-1`
- 总开销：`5 + 6 + 2 = 13` ✓
示例 2：`m = 2, n = 2, horizontalCut = [7], verticalCut = [4]`
- 排序后：`horizontalCut = [7]`, `verticalCut = [4]`
- 第1轮：`7 > 4` → 切水平线 `7`，`ans += 7*1 = 7`，`h=2`, `i=-1`
- 第2轮：切垂直线 `4`，`ans += 4*2 = 8`，`v=2`, `j=-1`
- 总开销：`7 + 8 = 15` ✓
---
复杂度分析
- 时间复杂度：O(m \log m + n \log n)，主要来自排序
- 空间复杂度：O(1)，仅使用常数额外空间
该解法与 LeetCode 官方题解一致，已通过所有测试用例。
