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

题解

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;
    }
};

思路

"切蛋糕的最小总开销 II" 对 "切蛋糕的最小总开销 I" 的数据做了增强，无法暴力求解。

借用了最小生成树思想，使用贪心法

image-ocrd.png

我们将水平切割和垂直切割的开销数组分别排序，将切割过程​逆向看作合并过程​。这样，在遍历时，算法的行为类似于最小生成树的 ​Kruskal 算法​，即每次选择当前最优的“边”（即切割）。

但与 Kruskal 算法不同的是，本问题中每次选择的“边”的权重是动态变化的。具体来说，当选择第 i 条水平切割时，如果已经有 j 条垂直切割被合并，那么这次切割的实际开销会乘以 (n - j)，因为当前剩余的列数为 n - j。同理，垂直切割的开销也会根据已合并的水平切割数动态调整。

这种动态权重的特性使得问题与传统的 MST 有所不同，但贪心思想的核心——每次选择当前最优解——仍然适用。