What is the core pattern in Minimum Cost for Cutting Cake II?

The problem relies on a greedy choice plus invariant validation pattern, choosing largest cuts first and tracking perpendicular segments.

Why must cuts be sorted before processing?

Sorting ensures the greedy approach picks the largest cost first, reducing total accumulated cost efficiently.

How do you calculate the cost of each cut?

Multiply the cut value by the current number of segments in the perpendicular direction to account for its impact on all affected pieces.

What common mistakes cause wrong answers?

Mistakes include miscounting segment multipliers, choosing cuts in wrong order, or forgetting to update segment counts after each cut.

Can this approach handle large m and n efficiently?

Yes, sorting followed by greedy selection runs in O((m+n) log(m+n)) time, which scales well for m, n up to 10^5.

#3219

Hard

auto_awesome贪心·invariant

LeetCode 题解工作台

切蛋糕的最小总开销 II

有一个 m x n 大小的矩形蛋糕，需要切成 1 x 1 的小块。给你整数 m ， n 和两个数组： horizontalCut 的大小为 m - 1 ，其中 horizontalCut[i] 表示沿着水平线 i 切蛋糕的开销。 verticalCut 的大小为 n - 1 ，其中 vertica…

数组贪心排序

题目描述

有一个 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⁵
horizontalCut.length == m - 1
verticalCut.length == n - 1
1 <= horizontalCut[i], verticalCut[i] <= 10³

lightbulb

解题思路

方法一：贪心 + 双指针

对于一个位置，越早切，所需要切的次数越少，因此，显然是开销越大的位置越早切。

所以，我们可以对数组 $\textit{horizontalCut}$ 和 $\textit{verticalCut}$ 按照从大到小的顺序排序，然后使用两个指针 $i$ 和 $j$ 分别指向 $\textit{horizontalCut}$ 和 $\textit{verticalCut}$ 的开销，每次选择开销较大的位置进行切割，同时更新对应的行数和列数。

每次在水平方向上切割时，如果此前列数为 $v$ ，那么此次的开销为 $\textit{horizontalCut}[i] \times v$ ，然后行数 $h$ 加一；同理，每次在垂直方向上切割时，如果此前行数为 $h$ ，那么此次的开销为 $\textit{verticalCut}[j] \times h$ ，然后列数 $v$ 加一。

最后，当 $i$ 和 $j$ 都到达末尾时，返回总开销即可。

时间复杂度 $O(m \times \log m + n \times \log n)$ ，空间复杂度 $O(\log m + \log n)$ 。其中 $m$ 和 $n$ 分别为 $\textit{horizontalCut}$ 和 $\textit{verticalCut}$ 的长度。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

class Solution:
    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
        h = 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] * v
                h, i = h + 1, i + 1
            else:
                ans += verticalCut[j] * h
                v, j = v + 1, j + 1
        return ans

speed

复杂度分析

指标	值
时间	complexity is O((m+n) log(m+n)) due to sorting both cut arrays. Space complexity is O(1) extra beyond the input arrays, as only segment counters and total cost need storage.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Asks how to prioritize horizontal vs vertical cuts based on cost impact.
question_mark
Checks if you correctly multiply each cut cost by the current perpendicular segment count.
question_mark
Probes understanding of cumulative cost tracking and failure modes when order is incorrect.

warning

常见陷阱

外企场景

error
Failing to sort the cuts and choosing suboptimal smaller costs first.
error
Incorrectly calculating cost by not accounting for current perpendicular segments.
error
Updating segment counts in wrong order leading to overcounted or undercounted total cost.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Cutting rectangles with arbitrary costs and different unit sizes.
arrow_right_alt
Maximizing revenue instead of minimizing cost with the same greedy approach.
arrow_right_alt
Adding a restriction on the number of allowable cuts in one direction.

help

常见问题

外企场景

继续练习

#3218 切蛋糕的最小总开销 I #3273 对 Bob 造成的最少伤害 #3281 范围内整数的最大得分