【Leetcode】3218. 切蛋糕的最小总开销 I

题目

题目链接🔗
有一个 $m\ast n$ 大小的矩形蛋糕，需要切成 $1\ast 1$ 的小块。

给你整数 $m$ ，$n$ 和两个数组：

$horizontalCut$ 的大小为 $m-1$ ，其中 $horizontalCut[i]$ 表示沿着水平线 $i$ 切蛋糕的开销。
$verticalCut$ 的大小为 $n-1$ ，其中 $verticalCut[j]$ 表示沿着垂直线 $j$ 切蛋糕的开销。
一次操作中，你可以选择任意不是 $1\ast 1$ 大小的矩形蛋糕并执行以下操作之一：

沿着水平线 $i$ 切开蛋糕，开销为 $horizontalCut[i]$ 。
沿着垂直线 $j$ 切开蛋糕，开销为 $verticalCut[j]$ 。
每次操作后，这块蛋糕都被切成两个独立的小蛋糕。

每次操作的开销都为最开始对应切割线的开销，并且不会改变。

请你返回将蛋糕全部切成 $1\ast 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. $1\le m,n\le 20$
2. $horizontalCut.length==m-1$
3. $verticalCut.length==n-1$
4. $1\le horizontalCut[i],verticalCut[i]\le 10^3$

思路

这个问题可以通过贪心算法来解决。我们需要在水平和垂直方向上进行切割，以确保每一块蛋糕都被分割出来。我们可以从最小的切割开始，逐步增加切割次数，直到满足所有的切割需求。

代码

class Solution {
public:int minimumCost(int m, int n, vector<int>& horizontalCut, vector<int>& verticalCut) {ranges::sort(horizontalCut,greater<int>());ranges::sort(verticalCut,greater<int>());int i=0,j=0,res=0;while(i<m-1&&j<n-1){if(horizontalCut[i]>verticalCut[j])res+=horizontalCut[i++]*(j+1);elseres+=verticalCut[j++]*(i+1);}while(i<m-1)res+=horizontalCut[i++]*n;while(j<n-1)res+=verticalCut[j++]*m;return res;}
};

复杂度分析

时间复杂度

$O((m+n)log(m+n))$，其中 $m$ 和 $n$ 分别是水平和垂直切割的数量。主要时间消耗在对水平和垂直切割位置的排序上。

空间复杂度

$O(1)$

结果

总结

本题是一个贪心算法的问题，关键在于理解如何通过贪心选择在每一步最小化切割次数。通过排序和贪心选择，我们可以解决