Hard

题目描述

有一块 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

示例 2：

输入：m = 2, n = 2, horizontalCut = [7], verticalCut = [4]
输出：15

提示：

  • 1 <= m, n <= 10^5
  • horizontalCut.length == m - 1
  • verticalCut.length == n - 1
  • 1 <= horizontalCut[i], verticalCut[i] <= 10^3

解题思路

解题思路

这道题的核心思路是贪心算法。关键观察是：当我们进行一次切割后，这条切割线会被后续的垂直切割重复使用。

具体分析：

  1. 当我们先进行一次水平切割时，蛋糕被分成两行。之后每次垂直切割都会在这两行上同时进行，相当于每次垂直切割的费用要乘以当前的行数。
  2. 同样，当我们先进行垂直切割时，每次后续的水平切割费用要乘以当前的列数。

贪心策略：

  • 总是优先选择费用最高的切割线进行切割
  • 使用两个指针分别指向已排序的水平和垂直切割数组
  • 维护当前的行数和列数，计算每次切割的实际费用

算法步骤：

  1. 将水平和垂直切割费用分别按降序排序
  2. 使用双指针技术，每次选择费用更高的切割方向
  3. 记录当前已有的行数和列数，计算总费用

这种贪心策略是最优的，因为费用高的切割线应该尽早执行，这样可以最小化后续切割的重复费用。

时间复杂度主要来自排序操作。

代码实现

class Solution {
public:
    long long minimumCost(int m, int n, vector<int>& horizontalCut, vector<int>& verticalCut) {
        sort(horizontalCut.rbegin(), horizontalCut.rend());
        sort(verticalCut.rbegin(), verticalCut.rend());
        
        long long cost = 0;
        int h = 0, v = 0;
        int rows = 1, cols = 1;
        
        while (h < horizontalCut.size() && v < verticalCut.size()) {
            if (horizontalCut[h] > verticalCut[v]) {
                cost += (long long)horizontalCut[h] * cols;
                rows++;
                h++;
            } else {
                cost += (long long)verticalCut[v] * rows;
                cols++;
                v++;
            }
        }
        
        while (h < horizontalCut.size()) {
            cost += (long long)horizontalCut[h] * cols;
            h++;
        }
        
        while (v < verticalCut.size()) {
            cost += (long long)verticalCut[v] * rows;
            v++;
        }
        
        return cost;
    }
};

class Solution:
    def minimumCost(self, m: int, n: int, horizontalCut: List[int], verticalCut: List[int]) -> int:
        horizontalCut.sort(reverse=True)
        verticalCut.sort(reverse=True)
        
        cost = 0
        h = v = 0
        rows = cols = 1
        
        while h < len(horizontalCut) and v < len(verticalCut):
            if horizontalCut[h] > verticalCut[v]:
                cost += horizontalCut[h] * cols
                rows += 1
                h += 1
            else:
                cost += verticalCut[v] * rows
                cols += 1
                v += 1
        
        while h < len(horizontalCut):
            cost += horizontalCut[h] * cols
            h += 1
            
        while v < len(verticalCut):
            cost += verticalCut[v] * rows
            v += 1
            
        return cost

public class Solution {
    public long MinimumCost(int m, int n, int[] horizontalCut, int[] verticalCut) {
        Array.Sort(horizontalCut, (a, b) => b.CompareTo(a));
        Array.Sort(verticalCut, (a, b) => b.CompareTo(a));
        
        long cost = 0;
        int h = 0, v = 0;
        int rows = 1, cols = 1;
        
        while (h < horizontalCut.Length && v < verticalCut.Length) {
            if (horizontalCut[h] > verticalCut[v]) {
                cost += (long)horizontalCut[h] * cols;
                rows++;
                h++;
            } else {
                cost += (long)verticalCut[v] * rows;
                cols++;
                v++;
            }
        }
        
        while (h < horizontalCut.Length) {
            cost += (long)horizontalCut[h] * cols;
            h++;
        }
        
        while (v < verticalCut.Length) {
            cost += (long)verticalCut[v] * rows;
            v++;
        }
        
        return cost;
    }
}

var minimumCost = function(m, n, horizontalCut, verticalCut) {
    horizontalCut.sort((a, b) => b - a);
    verticalCut.sort((a, b) => b - a);
    
    let cost = 0;
    let h = 0, v = 0;
    let rows = 1, cols = 1;
    
    while (h < horizontalCut.length && v < verticalCut.length) {
        if (horizontalCut[h] > verticalCut[v]) {
            cost += horizontalCut[h] * cols;
            rows++;
            h++;
        } else {
            cost += verticalCut[v] * rows;
            cols++;
            v++;
        }
    }
    
    while (h < horizontalCut.length) {
        cost += horizontalCut[h] * cols;
        h++;
    }
    
    while (v < verticalCut.length) {
        cost += verticalCut[v] * rows;
        v++;
    }
    
    return cost;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(m log m + n log n)主要来自对两个数组的排序操作
空间复杂度O(1)只使用了常数额外空间，不考虑排序的空间开销

相关题目