🔗 题目链接：3074. 重新分装苹果
📚 所属题单：灵茶山艾府 · 贪心算法题单 — §1.1 从最小/最大开始贪心
🏷️ 难度：Easy | 难度分：1198
🔖 标签：贪心、数组、排序

---

📖 题目描述

给你一个长度为 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
• 输入数据保证可以将包裹中的苹果重新分装到箱子中。

---

💡 思路分析

这题一句话就能说明白：大箱子优先装，能少用就少用！

想象一下你搬家打包——手边有大纸箱和小纸箱，你肯定先拿大箱子装，这样用的箱子最少对吧？这就是贪心的直觉。

举个栗子 🌰

apple = [1, 3, 2]，苹果总数 = 6

capacity = [4, 3, 1, 5, 2]，排序后从大到小：[5, 4, 3, 2, 1]

• 拿第 1 个箱子（容量 5）：剩余 6 - 5 = 1，还没装完
• 拿第 2 个箱子（容量 4）：剩余 1 - 4 = -3 ≤ 0，搞定了！

答案 = 2 个箱子 ✅

算法步骤

1. 算苹果总数：把 apple 数组求和
2. 箱子排序：把 capacity 从小到大排序（方便从数组末尾取最大值）
3. 从大到小装：依次用最大的箱子扣减苹果总数，扣到 ≤ 0 就返回用了几个箱子

---

✅ 代码实现（Java）

class Solution {
    public int minimumBoxes(int[] apple, int[] capacity) {
        // 第一步：计算苹果总数
        int total = 0;
        for (int a : apple) {
            total += a; // 把所有包裹里的苹果加起来
        }

        // 第二步：箱子容量排序（升序）
        // 排完序之后，最大的箱子在数组末尾
        Arrays.sort(capacity);

        // 第三步：从最大的箱子开始用，贪心地装苹果
        int count = 0; // 记录用了几个箱子
        for (int i = capacity.length - 1; i >= 0; i--) {
            total -= capacity[i]; // 用当前最大的箱子装苹果
            count++;              // 箱子数 +1
            if (total <= 0) {
                // 所有苹果都装完了，提前返回
                return count;
            }
        }

        // 题目保证一定能装完，所以理论上不会走到这里
        return count;
    }
}

---

📊 复杂度分析

	复杂度	说明
⏱️ 时间	O(m log m + n)	排序 capacity 需要 O(m log m)，求和 apple 需要 O(n)
💾 空间	O(log m)	排序的栈空间开销

---

🔗 参考

• 灵茶山艾府 · 排序+贪心 题解
• 灵茶山艾府 · 贪心算法题单

---

🍎 这道题是贪心入门题中的入门题，核心就一个字——排序后从大到小拿。如果你搬家的时候也这么干，恭喜你，你已经在用贪心算法了！