装满石头的背包的最大数量

标签: 贪心 数组 排序

难度: Medium

现有编号从 0 到 n - 1 的 n 个背包。给你两个下标从 0 开始的整数数组 capacity 和 rocks 。第 i 个背包最大可以装 capacity[i] 块石头，当前已经装了 rocks[i] 块石头。另给你一个整数 additionalRocks ，表示你可以放置的额外石头数量，石头可以往 任意 背包中放置。

请你将额外的石头放入一些背包中，并返回放置后装满石头的背包的 最大 数量。

示例 1：

输入：capacity = [2,3,4,5], rocks = [1,2,4,4], additionalRocks = 2
输出：3
解释：
1 块石头放入背包 0 ，1 块石头放入背包 1 。
每个背包中的石头总数是 [2,3,4,4] 。
背包 0 、背包 1 和 背包 2 都装满石头。
总计 3 个背包装满石头，所以返回 3 。
可以证明不存在超过 3 个背包装满石头的情况。
注意，可能存在其他放置石头的方案同样能够得到 3 这个结果。

示例 2：

输入：capacity = [10,2,2], rocks = [2,2,0], additionalRocks = 100
输出：3
解释：
8 块石头放入背包 0 ，2 块石头放入背包 2 。
每个背包中的石头总数是 [10,2,2] 。
背包 0 、背包 1 和背包 2 都装满石头。
总计 3 个背包装满石头，所以返回 3 。
可以证明不存在超过 3 个背包装满石头的情况。
注意，不必用完所有的额外石头。

提示：

  • n == capacity.length == rocks.length
  • 1 <= n <= 5 * 104
  • 1 <= capacity[i] <= 109
  • 0 <= rocks[i] <= capacity[i]
  • 1 <= additionalRocks <= 109

Submission

运行时间: 76 ms

内存: 22.8 MB

class Solution:
    def maximumBags(self, capacity: List[int], rocks: List[int], additionalRocks: int) -> int:
        n = len(capacity)
        gap = sum(capacity) - sum(rocks)
        gap -= additionalRocks
        if gap <= 0:
            return n

        arr = []
        for i in range(n):
            arr.append(capacity[i]-rocks[i])



        arr.sort(reverse=True)
        idx = 0
        while gap > 0:
            gap -= arr[idx]
            idx += 1

        return n - idx

Explain

此题解的思路是先计算出在不添加额外石头的情况下，所有背包的剩余容量之和（gap）。然后从剩余容量最大的背包开始，尝试用额外的石头填满这些背包。如果额外的石头足够填满所有背包，则返回背包的总数。如果不够，则返回填满的背包数量。

时间复杂度: O(n log n)

空间复杂度: O(n)

class Solution:
    def maximumBags(self, capacity: List[int], rocks: List[int], additionalRocks: int) -> int:
        n = len(capacity)
        gap = sum(capacity) - sum(rocks)  # 计算所有背包的剩余容量之和
        gap -= additionalRocks  # 减去额外的石头数量
        if gap <= 0:
            return n  # 如果额外的石头足以填满所有背包，则返回背包总数

        arr = []
        for i in range(n):
            arr.append(capacity[i]-rocks[i])  # 计算每个背包的剩余容量

        arr.sort(reverse=True)  # 对剩余容量进行降序排序
        idx = 0
        while gap > 0:
            gap -= arr[idx]  # 从剩余容量最大的背包开始，尝试用额外的石头填满
            idx += 1

        return n - idx  # 返回填满的背包数量

Explore

从剩余容量最大的背包开始填充的策略可以最快地降低剩余的总额外石头量。如果首先尝试填满最大的剩余容量，可以更快地达到无法继续填充的情况，从而确定无需继续尝试填充较小的容量背包。反之，如果先填较小的剩余容量，可能会导致使用了更多的额外石头也无法达到填满更多背包的效果，因为大容量背包可能仍然需要大量石头来填满。

在题解的算法中，背包的剩余容量为0意味着该背包已经完全填满了。在计算和排序过程中，这些背包的剩余容量为0，它们在排序后会自然排在数组的末端（如果使用降序排序）。因此，在遍历填充过程中，这些背包将自然被忽略，不会对填充其他背包产生影响。所以，没有必要在排序前显式排除这些背包。

遍历过程中停止添加石头的条件是当额外的石头无法继续填满当前考虑的背包时。在题解中，如果在任何时点额外石头的数量减到0或以下，且还有背包未被完全填满，就停止遍历。是有可能在不遍历完所有背包的情况下确定最终答案的，尤其是当额外石头足够填满所有背包或者额外石头在填充过程中用尽时。

题解的算法中已经考虑了额外石头正好等于所需填满石头的情况。在算法中，如果计算所有背包的剩余容量之和减去额外的石头之后的结果（gap）小于或等于0，这意味着额外的石头足够或正好填满所有背包。在这种情况下，算法会返回背包的总数。这种处理确保了即使额外的石头数量正好等于所需的总量，算法也能正确地返回所有背包都被填满的结果。