LeetCode 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(n\log n)O(nlogn)
• 空间复杂度O ( log ⁡ n ) O(\log n)O(logn)

AC代码

C++

/* * @LastEditTime: 2025-12-25 12:59:03 */typedeflonglongll;classSolution{public:llmaximumHappinessSum(vector<int>&happiness,intk){sort(happiness.begin(),happiness.end(),greater<>());ll ans=0;for(inti=0;i<k;i++){ans+=max(0,happiness[i]-i);}returnans;}};

C++

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

/* * @LastEditTime: 2025-12-25 13:00:12 */typedeflonglongll;classSolution{public:llmaximumHappinessSum(vector<int>&happiness,intk){sort(happiness.begin(),happiness.end(),greater<>());ll ans=0;for(inti=0;i<k;i++){happiness[i]-=i;if(happiness[i]<=0){returnans;}ans+=happiness[i];}returnans;}};

Python

''' LastEditTime: 2025-12-25 13:02:05 '''fromtypingimportListclassSolution:defmaximumHappinessSum(self,happiness:List[int],k:int)->int:returnsum(max(0,h-i)fori,hinenumerate(sorted(happiness,reverse=True)[:k]))

Java

/* * @LastEditTime: 2025-12-25 13:18:34 */importjava.util.Arrays;classSolution{publiclongmaximumHappinessSum(int[]happiness,intk){Arrays.sort(happiness);longans=0;intn=happiness.length;for(inti=0;i<k;i++){if(happiness[n-i-1]<=i){returnans;}ans+=happiness[n-i-1]-i;}returnans;}}

Go

/* * @LastEditTime: 2025-12-25 13:08:10 */packagemainimport"sort"funcmaximumHappinessSum(happiness[]int,kint)(ansint64){sort.Slice(happiness,func(i,jint)bool{returnhappiness[i]>happiness[j]})fori:=0;i<k;i++{happiness[i]-=iifhappiness[i]<=0{return}ans+=int64(happiness[i])}return}

Rust

/* * @LastEditTime: 2025-12-25 13:12:12 */implSolution{pubfnmaximum_happiness_sum(muthappiness:Vec<i32>,k:i32)->i64{letmutans:i64=0;happiness.sort_by(|a:&i32,b:&i32|b.cmp(a));foriin0..k{ifhappiness[iasusize]<=i{returnans;}ans+=(happiness[iasusize]-i)asi64;}ans}}

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

千篇源码题解已开源