列表

详情

100361. 切蛋糕的最小总开销 I

有一个 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: int minimumCost(int m, int n, vector<int>& horizontalCut, vector<int>& verticalCut) { } };

php 解法, 执行用时: 10 ms, 内存消耗: 20.2 MB, 提交时间: 2024-07-15 10:18:38 

class Solution {

    /**
     * @param Integer $m
     * @param Integer $n
     * @param Integer[] $horizontalCut
     * @param Integer[] $verticalCut
     * @return Integer
     */
    function minimumCost($m, $n, $horizontalCut, $verticalCut) {
        // 排序横切和竖切数组
        sort($horizontalCut);
        sort($verticalCut);
    
        $ans = 0;
        $i = $m - 2; // 因为最后一块不需要切，所以从倒数第二块开始
        $j = $n - 2; // 同理
    
        while ($i >= 0 || $j >= 0) {
            if ($j < 0 || ($i >= 0 && $horizontalCut[$i] > $verticalCut[$j])) {
                // 横切
                $ans += $horizontalCut[$i] * ($n - 1 - $j);
                $i--;
            } else {
                // 竖切
                $ans += $verticalCut[$j] * ($m - 1 - $i);
                $j--;
            }
        }
    
        return $ans;
    }
}

javascript 解法, 执行用时: 86 ms, 内存消耗: 51.1 MB, 提交时间: 2024-07-15 10:13:23 

/**
 * @param {number} m
 * @param {number} n
 * @param {number[]} horizontalCut
 * @param {number[]} verticalCut
 * @return {number}
 */
var minimumCost = function(m, n, horizontalCut, verticalCut) {
    // 对横切和竖切数组进行排序，从大到小
    horizontalCut.sort((a, b) => b - a);
    verticalCut.sort((a, b) => b - a);

    let ans = 0;
    let cntH = 1; // 需要横切的蛋糕块数
    let cntV = 1; // 需要竖切的蛋糕块数
    let i = 0; // 横切数组的索引
    let j = 0; // 竖切数组的索引

    // 循环直到所有的横切和竖切都被处理
    while (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 ans;
};

golang 解法, 执行用时: 2 ms, 内存消耗: 2.5 MB, 提交时间: 2024-07-15 10:10:50 

func minimumCost1(m, n int, horizontalCut, verticalCut []int) int {
	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 ans
}

// 优化
func minimumCost(m, n int, horizontalCut, verticalCut []int) int {
	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 ans
}

java 解法, 执行用时: 1 ms, 内存消耗: 41 MB, 提交时间: 2024-07-15 10:08:59 

class Solution {
    public int minimumCost1(int m, int n, int[] horizontalCut, int[] verticalCut) {
        Arrays.sort(horizontalCut); // 下面倒序遍历
        Arrays.sort(verticalCut);
        int 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 int minimumCost(int m, int n, int[] horizontalCut, int[] verticalCut) {
        Arrays.sort(horizontalCut); // 下面倒序遍历
        Arrays.sort(verticalCut);
        int 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 解法, 执行用时: 8 ms, 内存消耗: 28.9 MB, 提交时间: 2024-07-15 10:06:33 

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 解法, 执行用时: 44 ms, 内存消耗: 16.5 MB, 提交时间: 2024-07-15 10:05:33 

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

上一题

© 2024 leetcode.cn