LeetCode：3218. 切蛋糕的最小总开销 I（贪心 Java）

目录

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

题目描述：

实现代码与解析：

贪心

原理思路：

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 大小的矩形蛋糕并执行以下操作之一：

1. 沿着水平线 i 切开蛋糕，开销为 horizontalCut[i] 。
2. 沿着垂直线 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 <= 20
• horizontalCut.length == m - 1
• verticalCut.length == n - 1
• 1 <= horizontalCut[i], verticalCut[i] <= 103

实现代码与解析：

贪心

import java.util.Arrays;

class Solution {
    public int minimumCost(int m, int n, int[] horizontalCut, int[] verticalCut) {


        Arrays.sort(horizontalCut);
        Arrays.sort(verticalCut);

        int rs = m - 2, cs = n - 2;
        int cntR = 1; // 本次横向需要切的次数
        int cntC = 1; // 本次纵向需要切的次数
        int res=  0;
        while (rs >= 0 || cs >= 0) {
            if ( cs < 0 || (rs >= 0 && horizontalCut[rs] > verticalCut[cs])) { // 横向切
                res += horizontalCut[rs--] * cntC;
                cntR++;
            } else if (rs < 0 || (cs >= 0 && horizontalCut[rs] <= verticalCut[cs])) { // 纵向切
                res += verticalCut[cs--] * cntR;
                cntC++;
            }

        }
        return res;
    }
}

原理思路：

        因为无论如何每块的行与列都需要被切，所以每行和列开销最大的需要切的块数越少那么总开销就越少，所以每次切到时候选行和列中开销最大的行切即可。