切蛋糕的最小总开销II

2024-12-31

leetcode

题目：

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

提示：

1 <= m, n <= 105
horizontalCut.length == m - 1
verticalCut.length == n - 1
1 <= horizontalCut[i], verticalCut[i] <= 103

思路：

根据最小生成树的 Kruskal 算法，先把边权从小到大排序，然后遍历边，如果边的两个点属于不同连通块，则合并。

在上图中：
    由于 1 最小，把第一、二排的节点上下连边，也就是把 3 条边权为 1 的边加入生成树。
    对于 3，由于第一、二排的节点已经上下连边，所以只需把 2 条边权为 3 的边加入生成树。
    5 同理，把 2 条边权为 5 的边加入生成树。
    最后，对于 7，此时只剩下两个连通块，只需把 1 条边权为 7 的边加入生成树。

一般地，我们用双指针计算答案：
    从小到大排序两个数组。初始化 i=j=0。
    如果 horizontalCut[i] < verticalCut[j]，把 n−j 条边权为 horizontalCut[i] 的边加入答案，然后 i 加一。
    否则，把 m−i 条边权为 verticalCut[j] 的边加入答案，然后 j 加一。
    循环次数为两个数组的长度之和，即 (m−1) + (n−1) = m+n−2。

代码：

class Solution {
public:
    long long minimumCost(int m, int n, vector<int>& horizontalCut, vector<int>& verticalCut) {
        ranges::sort(horizontalCut);
        ranges::sort(verticalCut);
        long long ans = 0;
        int i = 0, j = 0;
        while (i < m - 1 || j < n - 1) {
            if (j == n - 1 || i < m - 1 && horizontalCut[i] < verticalCut[j]) {
                ans += horizontalCut[i++] * (n - j); // 上下连边
            } else {
                ans += verticalCut[j++] * (m - i); // 左右连边
            }
        }
        return ans;
    }
};