3075.幸福值最大化的选择方案：排序

【LetMeFly】3075.幸福值最大化的选择方案：排序

力扣题目链接：https://leetcode.cn/problems/maximize-happiness-of-selected-children/

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

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

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

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

 

示例 1：

输入：happiness = [1,2,3], k = 2
输出：4
解释：按以下方式选择 2 个孩子：
- 选择幸福值为 3 的孩子。剩余孩子的幸福值变为 [0,1] 。
- 选择幸福值为 1 的孩子。剩余孩子的幸福值变为 [0] 。注意幸福值不能小于 0 。
所选孩子的幸福值之和为 3 + 1 = 4 。

示例 2：

输入：happiness = [1,1,1,1], k = 2
输出：1
解释：按以下方式选择 2 个孩子：
- 选择幸福值为 1 的任意一个孩子。剩余孩子的幸福值变为 [0,0,0] 。
- 选择幸福值为 0 的孩子。剩余孩子的幸福值变为 [0,0] 。
所选孩子的幸福值之和为 1 + 0 = 1 。

示例 3：

输入：happiness = [2,3,4,5], k = 1
输出：5
解释：按以下方式选择 1 个孩子：
- 选择幸福值为 5 的孩子。剩余孩子的幸福值变为 [1,2,3] 。
所选孩子的幸福值之和为 5 。

 

提示：

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

解题方法：排序

题目翻译：

每个孩子都有一个价值，一次只能压榨一个孩子的价值。每剥夺一个孩子的价值，其他娃子都会因为受到惊吓而价值减一，一旦某娃子没有了使用价值就会被立刻丢弃。

问最多压榨k个娃子最多夺取多少总价值。

怎么选？当然是按照价值大的优先选。没被压榨过的娃子们也会随着时间的流逝人老珠黄，但是没办法，一次只能压榨一个。

让娃子们俺价值从大到小排个序，每次压榨一个，第几次压榨被压榨孩子的价值就会减少几减1。

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

AC代码

C++

/*
 * @LastEditTime: 2025-12-25 12:59:03
 */
typedef long long ll;
class Solution {
public:
    ll maximumHappinessSum(vector<int>& happiness, int k) {
        sort(happiness.begin(), happiness.end(), greater<>());
        ll ans = 0;
        for (int i = 0; i < k; i++) {
            ans += max(0, happiness[i] - i);
        }
        return ans;
    }
};

C++

当然，前娃都没价值的时候后娃子肯定也没价值了，可直接提前完工。

/*
 * @LastEditTime: 2025-12-25 13:00:12
 */
typedef long long ll;
class Solution {
public:
    ll maximumHappinessSum(vector<int>& happiness, int k) {
        sort(happiness.begin(), happiness.end(), greater<>());
        ll ans = 0;
        for (int i = 0; i < k; i++) {
            happiness[i] -= i;
            if (happiness[i] <= 0) {
                return ans;
            }
            ans += happiness[i];
        }
        return ans;
    }
};

Python

'''
LastEditTime: 2025-12-25 13:02:05
'''
from typing import List

class Solution:
    def maximumHappinessSum(self, happiness: List[int], k: int) -> int:
        return sum(max(0, h - i) for i, h in enumerate(sorted(happiness, reverse=True)[:k]))

Java

/*
 * @LastEditTime: 2025-12-25 13:18:34
 */
import java.util.Arrays;

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

Go

/*
 * @LastEditTime: 2025-12-25 13:08:10
 */
package main

import "sort"

func maximumHappinessSum(happiness []int, k int) (ans int64) {
    sort.Slice(happiness, func(i, j int) bool { return happiness[i] > happiness[j] })
    for i := 0; i < k; i++ {
        happiness[i] -= i
        if happiness[i] <= 0 {
            return
        }
        ans += int64(happiness[i])
    }
    return
}

Rust

/*
 * @LastEditTime: 2025-12-25 13:12:12
 */
impl Solution {
    pub fn maximum_happiness_sum(mut happiness: Vec<i32>, k: i32) -> i64 {
        let mut ans: i64 = 0;
        happiness.sort_by(|a: &i32, b: &i32| b.cmp(a));
        for i in 0..k {
            if happiness[i as usize] <= i {
                return ans;
            }
            ans += (happiness[i as usize] - i) as i64;
        }
        ans
    }
}

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

千篇源码题解已开源