列表

详情


100367. 切蛋糕的最小总开销 II

有一个 m x n 大小的矩形蛋糕,需要切成 1 x 1 的小块。

给你整数 m ,n 和两个数组:

一次操作中,你可以选择任意不是 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

解释:

总开销为 5 + 1 + 1 + 3 + 3 = 13 。

示例 2:

输入:m = 2, n = 2, horizontalCut = [7], verticalCut = [4]

输出:15

解释:

总开销为 7 + 4 + 4 = 15 。

 

提示:

原站题解

去查看

上次编辑到这里,代码来自缓存 点击恢复默认模板
class Solution { public: long long minimumCost(int m, int n, vector<int>& horizontalCut, vector<int>& verticalCut) { } };

golang 解法, 执行用时: 353 ms, 内存消耗: 8.5 MB, 提交时间: 2024-07-15 10:09:52

func minimumCost1(m, n int, horizontalCut, verticalCut []int) int64 {
	slices.SortFunc(horizontalCut, func(a, b int) int { return b - a })
	slices.SortFunc(verticalCut, func(a, b int) int { return b - a })
	ans := 0
	cntH, cntV := 1, 1
	i, j := 0, 0
	for i < m-1 || j < n-1 {
		if j == n-1 || i < m-1 && horizontalCut[i] > verticalCut[j] {
			ans += horizontalCut[i] * cntH // 横切
			i++
			cntV++ // 需要竖切的蛋糕块增加
		} else {
			ans += verticalCut[j] * cntV // 竖切
			j++
			cntH++ // 需要横切的蛋糕块增加
		}
	}
	return int64(ans)
}

// 优化
func minimumCost(m, n int, horizontalCut, verticalCut []int) int64 {
	slices.SortFunc(horizontalCut, func(a, b int) int { return b - a })
	slices.SortFunc(verticalCut, func(a, b int) int { return b - a })
	ans := 0
	i, j := 0, 0
	for i < m-1 || j < n-1 {
		if j == n-1 || i < m-1 && horizontalCut[i] > verticalCut[j] {
			ans += horizontalCut[i] * (j + 1) // 横切
			i++
		} else {
			ans += verticalCut[j] * (i + 1) // 竖切
			j++
		}
	}
	return int64(ans)
}

java 解法, 执行用时: 91 ms, 内存消耗: 61.5 MB, 提交时间: 2024-07-15 10:07:54

class Solution {
    public long minimumCost1(int m, int n, int[] horizontalCut, int[] verticalCut) {
        Arrays.sort(horizontalCut); // 下面倒序遍历
        Arrays.sort(verticalCut);
        long ans = 0;
        int i = m - 2;
        int j = n - 2;
        int cntH = 1;
        int cntV = 1;
        while (i >= 0 || j >= 0) {
            if (j < 0 || i >= 0 && horizontalCut[i] > verticalCut[j]) {
                ans += horizontalCut[i--] * cntH; // 横切
                cntV++; // 需要竖切的蛋糕块增加
            } else {
                ans += verticalCut[j--] * cntV; // 竖切
                cntH++; // 需要横切的蛋糕块增加
            }
        }
        return ans;
    }

    // 优化
    public long minimumCost(int m, int n, int[] horizontalCut, int[] verticalCut) {
        Arrays.sort(horizontalCut); // 下面倒序遍历
        Arrays.sort(verticalCut);
        long ans = 0;
        int i = m - 2;
        int j = n - 2;
        while (i >= 0 || j >= 0) {
            if (j < 0 || i >= 0 && horizontalCut[i] > verticalCut[j]) {
                ans += horizontalCut[i--] * (n - 1 - j); // 横切
            } else {
                ans += verticalCut[j--] * (m - 1 - i); // 竖切
            }
        }
        return ans;
    }
}

cpp 解法, 执行用时: 417 ms, 内存消耗: 227.2 MB, 提交时间: 2024-07-15 10:06:21

class Solution {
public:
    long long minimumCost1(int m, int n, vector<int>& horizontalCut, vector<int>& verticalCut) {
        ranges::sort(horizontalCut, greater<>());
        ranges::sort(verticalCut, greater<>());
        long long ans = 0;
        int cnt_h = 1, cnt_v = 1;
        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++] * cnt_h; // 横切
                cnt_v++; // 需要竖切的蛋糕块增加
            } else {
                ans += verticalCut[j++] * cnt_v; // 竖切
                cnt_h++; // 需要横切的蛋糕块增加
            }
        }
        return ans;
    }

    // 优化
    long long minimumCost(int m, int n, vector<int>& horizontalCut, vector<int>& verticalCut) {
        ranges::sort(horizontalCut, greater<>());
        ranges::sort(verticalCut, greater<>());
        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++] * (j + 1); // 横切
            } else {
                ans += verticalCut[j++] * (i + 1); // 竖切
            }
        }
        return ans;
    }
};

python3 解法, 执行用时: 578 ms, 内存消耗: 28.6 MB, 提交时间: 2024-07-15 10:05:18

class Solution:
    # 谁开销大,先切谁,留到后面只会开销更大
    def minimumCost1(self, m: int, n: int, horizontalCut: List[int], verticalCut: List[int]) -> int:
        horizontalCut.sort(reverse=True)
        verticalCut.sort(reverse=True)
        ans = i = j = 0
        cnt_h = cnt_v = 1
        while i < m - 1 or j < n - 1:
            if j == n - 1 or i < m - 1 and horizontalCut[i] > verticalCut[j]:
                ans += horizontalCut[i] * cnt_h  # 横切
                i += 1
                cnt_v += 1  # 需要竖切的蛋糕块增加
            else:
                ans += verticalCut[j] * cnt_v  # 竖切
                j += 1
                cnt_h += 1  # 需要横切的蛋糕块增加
        return ans
        
    # 优化
    def minimumCost(self, m: int, n: int, horizontalCut: List[int], verticalCut: List[int]) -> int:
        horizontalCut.sort(reverse=True)
        verticalCut.sort(reverse=True)
        ans = i = j = 0
        while i < m - 1 or j < n - 1:
            if j == n - 1 or i < m - 1 and horizontalCut[i] > verticalCut[j]:
                ans += horizontalCut[i] * (j + 1)  # 横切
                i += 1
            else:
                ans += verticalCut[j] * (i + 1)  # 竖切
                j += 1
        return ans

上一题