3074. 苹果重新分装到盒子里

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
输入保证可以将苹果包重新分装到盒子里。

解题思路

这是一个典型的贪心算法问题。我们的目标是用最少的盒子装下所有苹果。

解题思路：

计算苹果总数：首先统计所有苹果包中苹果的总数量。
贪心策略：为了使用最少的盒子，我们应该优先选择容量最大的盒子。这样可以最快地减少剩余需要装的苹果数量。
排序优化：将盒子按容量从大到小排序，然后依次选择盒子，直到所有苹果都能装下。
累计容量：从容量最大的盒子开始，累计已选盒子的总容量，当总容量大于等于苹果总数时，返回已选盒子的数量。

算法步骤：

计算苹果总数
对盒子容量进行降序排序
贪心地选择容量最大的盒子，直到总容量足够装下所有苹果
返回所需的最少盒子数量

这种贪心策略的正确性基于：要用最少盒子装下固定数量的物品，应该优先使用容量最大的盒子。

代码实现

class Solution {
public:
    int minimumBoxes(vector<int>& apple, vector<int>& capacity) {
        // 计算苹果总数
        int totalApples = 0;
        for (int a : apple) {
            totalApples += a;
        }
        
        // 按容量降序排序
        sort(capacity.begin(), capacity.end(), greater<int>());
        
        // 贪心选择容量最大的盒子
        int boxes = 0;
        int currentCapacity = 0;
        
        for (int cap : capacity) {
            currentCapacity += cap;
            boxes++;
            if (currentCapacity >= totalApples) {
                return boxes;
            }
        }
        
        return boxes;
    }
};

class Solution:
    def minimumBoxes(self, apple: List[int], capacity: List[int]) -> int:
        # 计算苹果总数
        total_apples = sum(apple)
        
        # 按容量降序排序
        capacity.sort(reverse=True)
        
        # 贪心选择容量最大的盒子
        boxes = 0
        current_capacity = 0
        
        for cap in capacity:
            current_capacity += cap
            boxes += 1
            if current_capacity >= total_apples:
                return boxes
        
        return boxes

public class Solution {
    public int MinimumBoxes(int[] apple, int[] capacity) {
        // 计算苹果总数
        int totalApples = apple.Sum();
        
        // 按容量降序排序
        Array.Sort(capacity, (a, b) => b.CompareTo(a));
        
        // 贪心选择容量最大的盒子
        int boxes = 0;
        int currentCapacity = 0;
        
        foreach (int cap in capacity) {
            currentCapacity += cap;
            boxes++;
            if (currentCapacity >= totalApples) {
                return boxes;
            }
        }
        
        return boxes;
    }
}

/**
 * @param {number[]} apple
 * @param {number[]} capacity
 * @return {number}
 */
var minimumBoxes = function(apple, capacity) {
    // 计算苹果总数
    const totalApples = apple.reduce((sum, a) => sum + a, 0);
    
    // 按容量降序排序
    capacity.sort((a, b) => b - a);
    
    // 贪心选择容量最大的盒子
    let boxes = 0;
    let currentCapacity = 0;
    
    for (const cap of capacity) {
        currentCapacity += cap;
        boxes++;
        if (currentCapacity >= totalApples) {
            return boxes;
        }
    }
    
    return boxes;
};

在 LeetCode 上运行：力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型	大小
时间复杂度	O(n + m log m)，其中 n 是苹果包数量，m 是盒子数量。计算苹果总数需要 O(n)，排序需要 O(m log m)，遍历盒子需要 O(m)
空间复杂度	O(1)，只使用了常数额外空间（不考虑排序的空间复杂度）

题目描述#

解题思路#

代码实现#

复杂度分析#

题目描述

解题思路

代码实现

复杂度分析