[LeetCode] 3075. Maximize Happiness of Selected Children

You are given an array happiness of length n, and a positive integer k.

There are n children standing in a queue, where the ith child has happiness value happiness[i]. You want to select k children from these n children in k turns.

In each turn, when you select a child, the happiness value of all the children that have not been selected till now decreases by 1. Note that the happiness value cannot become negative and gets decremented only if it is positive.

Return the maximum sum of the happiness values of the selected children you can achieve by selecting k children.

Example 1:
Input: happiness = [1,2,3], k = 2
Output: 4
Explanation: We can pick 2 children in the following way:

• Pick the child with the happiness value == 3. The happiness value of the remaining children becomes [0,1].
• Pick the child with the happiness value == 1. The happiness value of the remaining child becomes [0]. Note that the happiness value cannot become less than 0.
  The sum of the happiness values of the selected children is 3 + 1 = 4.

Example 2:
Input: happiness = [1,1,1,1], k = 2
Output: 1
Explanation: We can pick 2 children in the following way:

• Pick any child with the happiness value == 1. The happiness value of the remaining children becomes [0,0,0].
• Pick the child with the happiness value == 0. The happiness value of the remaining child becomes [0,0].
  The sum of the happiness values of the selected children is 1 + 0 = 1.

Example 3:
Input: happiness = [2,3,4,5], k = 1
Output: 5
Explanation: We can pick 1 child in the following way:

• Pick the child with the happiness value == 5. The happiness value of the remaining children becomes [1,2,3].
  The sum of the happiness values of the selected children is 5.

Constraints:
1 <= n == happiness.length <= 2 * 105
1 <= happiness[i] <= 108
1 <= k <= n

幸福值最大化的选择方案。

给你一个长度为 n 的数组 happiness ，以及一个 正整数 k 。

n 个孩子站成一队，其中第 i 个孩子的 幸福值 是 happiness[i] 。你计划组织 k 轮筛选从这 n 个孩子中选出 k 个孩子。

在每一轮选择一个孩子时，所有 尚未 被选中的孩子的 幸福值 将减少 1 。注意，幸福值 不能 变成负数，且只有在它是正数的情况下才会减少。

选择 k 个孩子，并使你选中的孩子幸福值之和最大，返回你能够得到的 最大值 。

思路

思路是排序。把 input 数组排序，之后按照从大到小开始扫描数组。每遇到一个孩子的时候，先按照规则将他的幸福值减去相应的数值，比如之前已经选择了 X 个孩子，就需要把当前孩子的幸福值 - X。做过这个减法之后，如果当前孩子的幸福值还大于 0 的话，就把当前孩子的幸福值累加到结果里。

复杂度

时间O(nlogn)
空间O(1)

代码

Java实现

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