3074.重新分装苹果：排序

【LetMeFly】3074.重新分装苹果：排序

力扣题目链接：https://leetcode.cn/problems/apple-redistribution-into-boxes/

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

解题方法：排序

每个苹果都要有它的归宿，一共有多少个苹果呢？算一算就知道了。

如何使用最少的箱子？当然是用尽可能大的箱子！

把箱子从大到小排个序，遍历箱子并依次消费苹果，直到苹果消费完毕。

• 时间复杂度$O(n+m\log m)$
• 空间复杂度$O(\log m)$

AC代码

C++

/*
 * @LastEditTime: 2025-12-24 13:32:26
 */
class Solution {
public:
    int minimumBoxes(vector<int>& apple, vector<int>& capacity) {
        sort(capacity.begin(), capacity.end(), greater<>());
        int cnt = 0;
        for (int t : apple) {
            cnt += t;
        }
        int ans = 0;
        for (int t : capacity) {
            cnt -= t;
            ans++;
            if (cnt <= 0) {
                return ans;
            }
        }
        return -1;  // Fake Return
    }
};

Python

'''
LastEditTime: 2025-12-24 13:40:50
'''
from typing import List

class Solution:
    def minimumBoxes(self, apple: List[int], capacity: List[int]) -> int:
        cnt = sum(apple)
        ans = 0
        for t in sorted(capacity, reverse=True):
            cnt -= t
            ans += 1
            if cnt <= 0:
                return ans


# if __name__ == "__main__":
#     sol = Solution()
#     print(sol.minimumBoxes([1,3,2], [4,3,1,5,2]))

Java

/*
 * @LastEditTime: 2025-12-24 18:35:17
 */
import java.util.Arrays;

class Solution {
    public int minimumBoxes(int[] apple, int[] capacity) {
        int cnt = 0;
        for (int t : apple) {
            cnt += t;
        }
        Arrays.sort(capacity);
        int ans = 0;
        for (int i = capacity.length - 1; i >= 0; i--) {
            cnt -= capacity[i];
            ans++;
            if (cnt <= 0) {
                return ans;
            }
        }
        return -1;  // FAKE RETURN
    }
}

Go

/*
 * @LastEditTime: 2025-12-24 13:45:02
 */
package main

import "sort"

func minimumBoxes(apple []int, capacity []int) int {
    cnt := 0
    for _, t := range apple {
        cnt += t
    }
    sort.Sort(sort.Reverse(sort.IntSlice(capacity)))
    for i, t := range capacity {
        cnt -= t
        if cnt <= 0 {
            return i + 1
        }
    }
    return -1  // Fake Return
}

Rust

/*
 * @LastEditTime: 2025-12-24 18:47:13
 */
impl Solution {
    pub fn minimum_boxes(apple: Vec<i32>, mut capacity: Vec<i32>) -> i32 {
        let mut cnt: i32 = 0;
        for t in apple.iter() {
            cnt += t;
        }
        capacity.sort_by(|a, b| b.cmp(a));

        let mut ans: i32 = 0;
        for t in capacity.iter() {
            cnt -= t;
            ans += 1;
            if cnt <= 0 {
                return ans
            }
        }
        ans
    }
}

End

Merry Christmas？

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~

千篇源码题解已开源