【Leetcode 每日一题】3218. 切蛋糕的最小总开销 I

问题背景

有一个 $m\times n$ 大小的矩形蛋糕，需要切成 $1\times 1$ 的小块。
给你整数 $m,n$ 和两个数组：

• $horizontalCut$ 的大小为 $m-1$，其中 $horizontalCut[i]$ 表示沿着水平线 $i$ 切蛋糕的开销。
• $verticalCut$ 的大小为 $n-1$，其中 $verticalCut[j]$ 表示沿着垂直线 $j$ 切蛋糕的开销。

一次操作中，你可以选择任意不是 $1\times 1$ 大小的矩形蛋糕并执行以下操作之一：

• 沿着水平线 $i$ 切开蛋糕，开销为 $horizontalCut[i]$。
• 沿着垂直线 $j$ 切开蛋糕，开销为 $verticalCut[j]$。

每次操作后，这块蛋糕都被切成两个独立的小蛋糕。
每次操作的开销都为最开始对应切割线的开销，并且不会改变。
请你返回将蛋糕全部切成 $1\times 1$ 的蛋糕块的 最小 总开销。

数据约束

• $1\times m,n\times 20$
• $horizontalCut.length=m-1$
• $verticalCut.length=n-1$
• $1\le horizontalCut[i],verticalCut[i]\le 10^3$

解题过程

自己考虑的时候想的是贪心算法，心里没底而且还没写对。
看了下 灵神的题解 之后发现能转化成最小生成树来解决，那就不用担心正确性的问题，$Kruskal$算法相对来说还是比较好写的。

具体实现

class Solution {
    public int minimumCost(int m, int n, int[] horizontalCut, int[] verticalCut) {
        Arrays.sort(horizontalCut);
        Arrays.sort(verticalCut);
        int res = 0;
        for(int i = 0, j = 0; i < m - 1 || j < n - 1;) {
            // 如果没有纵向的选择，或者尚有横向边并且它是当前权值最小的，累计进入答案
            // 注意 Java 中逻辑与比逻辑或优先级要高，这里如果没有发生或运算短路，要先计算与
            if(j == n - 1 || i < m - 1 && horizontalCut[i] < verticalCut[j]) {
                // j 同时也表示已经选择的纵向边数量，当前选择的横向边的数量应为 (n - j)
                res += horizontalCut[i++] * (n - j);
            } else {
                // i 同时也表示已经选择的纵向边数量，当前选择的横向边的数量应为 (m - i)
                res += verticalCut[j++] * (m - i);
            }
        }
        return res;
    }
}

原文地址：https://blog.csdn.net/2401_88859777/article/details/144713821

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！