当前位置：首页 > article >正文

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

article 2024/12/26 7:39:37

文章目录

题目
思路
代码
复杂度分析
- 时间复杂度
- 空间复杂度
结果
总结

题目

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

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

$h or i zo n t a lC u t$ 的大小为 $m - 1$ ，其中 $h or i zo n t a lC u t [i]$ 表示沿着水平线 $i$ 切蛋糕的开销。
$v er t i c a lC u t$ 的大小为 $n - 1$ ，其中 $v er t i c a lC u t [j]$ 表示沿着垂直线 $j$ 切蛋糕的开销。
一次操作中，你可以选择任意不是 $1 * 1$ 大小的矩形蛋糕并执行以下操作之一：

沿着水平线 $i$ 切开蛋糕，开销为 $h or i zo n t a lC u t [i]$ 。
沿着垂直线 $j$ 切开蛋糕，开销为 $v er t i c a lC u t [j]$ 。
每次操作后，这块蛋糕都被切成两个独立的小蛋糕。

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

请你返回将蛋糕全部切成 $1 * 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 。

提示：

$\leq m, n \leq 20$
$h or i zo n t a lC u t . l e n g t h == m - 1$
$v er t i c a lC u t . l e n g t h == n - 1$
$\leq horizontalCut[i], verticalCut[i] \leq 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);
            else
                res+=verticalCut[j++]*(i+1);
        }
        while(i<m-1)
            res+=horizontalCut[i++]*n;
        while(j<n-1)
            res+=verticalCut[j++]*m;
        return res;
    }
};