【贪心】力扣3218. 切蛋糕的最小总开销 I

有一个 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 。

贪心

class Solution {
public:
    int minimumCost(int m, int n, vector<int>& horizontalCut, vector<int>& verticalCut) {
        int a = 1;
        int b = 1;
        sort(horizontalCut.begin(), horizontalCut.end(), greater<int>());
        sort(verticalCut.begin(), verticalCut.end(), greater<int>());
        int x = 0, y = 0;
        int ans = 0;
        while(x < m-1 && y < n-1){
            if(horizontalCut[x] > verticalCut[y]){
                ans += b * horizontalCut[x];
                a++;
                x++;
            }
            else{
                ans += a * verticalCut[y];
                b++;
                y++;
            }
        }
        
        while (x < horizontalCut.size()) {
            ans += b * horizontalCut[x];
            x++;
        }

        while (y < verticalCut.size()) {
            ans += a * verticalCut[y];
            y++;
        }
        return ans;
    }
};

这道题使用贪心算法是最高效的做法，我们观察题目，假设我们每一次沿着水平线都切到底，那么沿着该水平线切的次数就是垂直方向有多少块蛋糕，那么开销就要乘以垂直方向蛋糕的数量。那么也就是说我们应该优先沿着开销大的水平线切，否则放到后面切的话，可能该水平线切到底的开销就要乘以更多的倍数。

所以我们将horizontalCut和verticalCut进行降序排序，然后我们去寻找horizontalCut和verticalCut中的最大水平线开销来作为当前切哪一刀。当两个数组中的任意一个遍历完后，都会跳出while循环。由于另外一组数组还没有完全遍历，所以我们要继续计算剩余的开销。

在这道题中我们定义一个变量ans来记录切蛋糕的最小开销是多少，最后返回ans。