方法一：贪心 + 排序

为了使得幸福值之和尽可能大，我们应该优先选择幸福值大的孩子。因此，我们可以对孩子按照幸福值从大到小排序，然后依次选择 $k$ 个孩子。对于当前第 $i$ 个孩子，能够得到的幸福值为 $\max(\textit{happiness}[i] - i, 0)$，最后返回这 $k$ 个孩子的幸福值之和。

###python

class Solution:
    def maximumHappinessSum(self, happiness: List[int], k: int) -> int:
        happiness.sort(reverse=True)
        ans = 0
        for i, x in enumerate(happiness[:k]):
            x -= i
            ans += max(x, 0)
        return ans

###java

class Solution {
    public long maximumHappinessSum(int[] happiness, int k) {
        Arrays.sort(happiness);
        long ans = 0;
        for (int i = 0, n = happiness.length; i < k; ++i) {
            int x = happiness[n - i - 1] - i;
            ans += Math.max(x, 0);
        }
        return ans;
    }
}

###cpp

class Solution {
public:
    long long maximumHappinessSum(vector<int>& happiness, int k) {
        sort(happiness.rbegin(), happiness.rend());
        long long ans = 0;
        for (int i = 0, n = happiness.size(); i < k; ++i) {
            int x = happiness[i] - i;
            ans += max(x, 0);
        }
        return ans;
    }
};

###go

func maximumHappinessSum(happiness []int, k int) (ans int64) {
sort.Ints(happiness)
for i := 0; i < k; i++ {
x := happiness[len(happiness)-i-1] - i
ans += int64(max(x, 0))
}
return
}

###ts

function maximumHappinessSum(happiness: number[], k: number): number {
    happiness.sort((a, b) => b - a);
    let ans = 0;
    for (let i = 0; i < k; ++i) {
        const x = happiness[i] - i;
        ans += Math.max(x, 0);
    }
    return ans;
}

###rust

impl Solution {
    pub fn maximum_happiness_sum(mut happiness: Vec<i32>, k: i32) -> i64 {
        happiness.sort_unstable_by(|a, b| b.cmp(a));

        let mut ans: i64 = 0;
        for i in 0..(k as usize) {
            let x = happiness[i] as i64 - i as i64;
            if x > 0 {
                ans += x;
            }
        }
        ans
    }
}

###cs

public class Solution {
    public long MaximumHappinessSum(int[] happiness, int k) {
        Array.Sort(happiness, (a, b) => b.CompareTo(a));
        long ans = 0;
        for (int i = 0; i < k; i++) {
            int x = happiness[i] - i;
            if (x <= 0) {
                break;
            }
            ans += x;
        }
        return ans;
    }
}

时间复杂度 $O(n \times \log n + k)$，空间复杂度 $O(\log n)$。其中 $n$ 是数组 $\textit{happiness}$ 的长度。

有任何问题，欢迎评论区交流，欢迎评论区提供其它解题思路（代码），也可以点个赞支持一下作者哈 😄~

方法一：贪心 + 排序

为了使得需要的箱子数量尽可能少，我们应该优先使用容量大的箱子。因此，我们可以对箱子按照容量从大到小排序，然后依次使用箱子，直到所有的苹果都被分装完，返回此时使用的箱子数量。

###python

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

###java

class Solution {
    public int minimumBoxes(int[] apple, int[] capacity) {
        Arrays.sort(capacity);
        int s = 0;
        for (int x : apple) {
            s += x;
        }
        for (int i = 1, n = capacity.length;; ++i) {
            s -= capacity[n - i];
            if (s <= 0) {
                return i;
            }
        }
    }
}

###cpp

class Solution {
public:
    int minimumBoxes(vector<int>& apple, vector<int>& capacity) {
        sort(capacity.rbegin(), capacity.rend());
        int s = accumulate(apple.begin(), apple.end(), 0);
        for (int i = 1;; ++i) {
            s -= capacity[i - 1];
            if (s <= 0) {
                return i;
            }
        }
    }
};

###go

func minimumBoxes(apple []int, capacity []int) int {
sort.Ints(capacity)
s := 0
for _, x := range apple {
s += x
}
for i := 1; ; i++ {
s -= capacity[len(capacity)-i]
if s <= 0 {
return i
}
}
}

###ts

function minimumBoxes(apple: number[], capacity: number[]): number {
    capacity.sort((a, b) => b - a);
    let s = apple.reduce((acc, cur) => acc + cur, 0);
    for (let i = 1; ; ++i) {
        s -= capacity[i - 1];
        if (s <= 0) {
            return i;
        }
    }
}

###rust

impl Solution {
    pub fn minimum_boxes(apple: Vec<i32>, mut capacity: Vec<i32>) -> i32 {
        capacity.sort();

        let mut s: i32 = apple.iter().sum();

        let n = capacity.len();
        let mut i = 1;
        loop {
            s -= capacity[n - i];
            if s <= 0 {
                return i as i32;
            }
            i += 1;
        }
    }
}

时间复杂度 $O(m \times \log m + n)$，空间复杂度 $O(\log m)$。其中 $m$ 和 $n$ 分别是数组 $\textit{capacity}$ 和 $\textit{apple}$ 的长度。

有任何问题，欢迎评论区交流，欢迎评论区提供其它解题思路（代码），也可以点个赞支持一下作者哈 😄~