重新分装苹果

难度: Easy

给你一个长度为 n 的数组 apple 和另一个长度为 m 的数组 capacity 。

一共有 n 个包裹，其中第 i 个包裹中装着 apple[i] 个苹果。同时，还有 m 个箱子，第 i 个箱子的容量为 capacity[i] 个苹果。

请你选择一些箱子来将这 n 个包裹中的苹果重新分装到箱子中，返回你需要选择的箱子的最小数量。

注意，同一个包裹中的苹果可以分装到不同的箱子中。

示例 1：

输入：apple = [1,3,2], capacity = [4,3,1,5,2]
输出：2
解释：使用容量为 4 和 5 的箱子。
总容量大于或等于苹果的总数，所以可以完成重新分装。

示例 2：

输入：apple = [5,5,5], capacity = [2,4,2,7]
输出：4
解释：需要使用所有箱子。

提示：

1 <= n == apple.length <= 50
1 <= m == capacity.length <= 50
1 <= apple[i], capacity[i] <= 50
输入数据保证可以将包裹中的苹果重新分装到箱子中。

Submission

运行时间: 19 ms

内存: 16.1 MB

class Solution:
    def minimumBoxes(self, apple: List[int], capacity: List[int]) -> int:
        t=sum(apple)
        capacity.sort(reverse=True)
        for i,c in enumerate(capacity):
            t-=c
            if t<=0:return i+1
        return len(capacity)

Explain

该题解的主要思路是首先计算所有包裹中苹果的总数，然后将箱子的容量数组进行降序排序。通过遍历排序后的箱子容量数组，逐一从苹果总数中减去每个箱子的容量，直到苹果总数小于或等于零。这样，我们就能得到所需的最小箱子数量。该方法的核心在于优先使用容量大的箱子，以最大化每次装箱的苹果数量，从而减少所需箱子的数量。

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

空间复杂度: O(m)

class Solution:
    def minimumBoxes(self, apple: List[int], capacity: List[int]) -> int:
        t = sum(apple)  # 计算所有苹果的总数
        capacity.sort(reverse=True)  # 将箱子容量降序排序
        for i, c in enumerate(capacity):  # 遍历每个箱子
            t -= c  # 从苹果总数中减去当前箱子的容量
            if t <= 0: return i + 1  # 如果苹果已全部装箱，返回所用箱子数量
        return len(capacity)  # 如果所有箱子容量加起来仍不足以装下所有苹果，返回箱子总数

Explore

在Python中，整数的类型是动态的，可以自动处理非常大的数值，因为Python整数类型 (`int`) 在需要时可以自动转换为长整数类型 (`long`)，这几乎没有限制。因此，即使苹果的总数非常大，超出了传统意义上的32位或64位整数的最大值，Python仍然可以正确处理这些数值，无需担心溢出问题。

降序排序箱子的容量是基于贪心算法的思想，目的是尽可能快地减少苹果总数。通过优先使用容量最大的箱子，可以在使用较少的箱子数目的情况下装下更多的苹果。这种方法在求解最小箱子数目问题时是有效的，因为每一步都尽可能最大地减少剩余苹果数，从而达到整体的最优解。

容量为0的箱子对于装苹果没有任何贡献，可以在算法实际运行前从容量数组中移除，或者在遍历容量时简单地忽略这些箱子。这样做不会影响算法的正确性或最终结果，因为这些箱子不会对减少苹果总数或计算所需箱子数量产生任何影响。