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

链接：3219.切蛋糕的最小总开销II
难度：Hard
标签：贪心、数组、排序
简介：请你返回将蛋糕全部切成 1 x 1 的蛋糕块的 最小 总开销。

题解 1 - python

• 编辑时间：2024-12-31
• 执行用时：1107ms
• 内存消耗：46.13MB
• 编程语言：python
• 解法介绍：贪心每次切成本最大的

class Solution:
    def minimumCost(self, n: int, m: int, horizontalCut: List[int], verticalCut: List[int]) -> int:
        res = 0
        hcnt = vcnt = 1
        q = sorted([(horizontalCut[i], 0) for i in range(n - 1)] + [(verticalCut[j], 1) for j in range(m - 1)], reverse = True)
        for cost, ty in q:
            cnt = vcnt if ty else hcnt
            res += cost * cnt
            if ty: hcnt += 1
            else: vcnt += 1
        return res