2024-09-04：用go语言，给定一个长度为n的数组 happiness，表示每个孩子的幸福值，以及一个正整数k，我们需要从这n个孩子中选出k个孩子。
在筛选过程中，每轮选择一个孩子时，所有尚未选中的孩子的幸福值都会减少 1。需要注意的是，幸福值不能降低到负数，只有在其为正数时才能减少。
我们的目标是尽可能使选中的k个孩子的幸福值之和最大化。
输入：happiness = [1,2,3], k = 2。
输出：4。
解释：按以下方式选择 2 个孩子：
1.选择幸福值为 3 的孩子。剩余孩子的幸福值变为 [0,1] 。
2.选择幸福值为 1 的孩子。剩余孩子的幸福值变为 [0] 。注意幸福值不能小于 0 。
所选孩子的幸福值之和为 3 1 = 4 。
答案2024-09-04：
chatgpt
题目来自leetcode3075。
大体步骤如下：
1.对孩子的幸福值数组 happiness 进行降序排序。
2.从排序后的数组中选择前 k 个幸福值最高的孩子。这些孩子的幸福值之和即为所求。
3.在选出的 k 个孩子中，逐个孩子判断幸福值是否大于等于当前所在位置的索引值，如果是，将幸福值与当前索引值相减，并累加到最终的结果中，表示该孩子的贡献幸福值。
4.最终返回累加的结果作为最大化幸福值之和的输出。
时间复杂度分析：
- • 排序的时间复杂度为 O(n*log(n))，n 为孩子的数量。
- • 选 k 个孩子时，需要遍历最多 k 个元素，时间复杂度为 O(k)。
- • 因此，总的时间复杂度为 O(n*log(n) k)。
空间复杂度分析：
- • 需要常量级别的额外空间来进行计算，因此总的额外空间复杂度可以看作是 O(1)。
Go完整代码如下：
代码语言：javascript复制package main
import(
"fmt"
"slices"
)
func maximumHappinessSum(happiness []int, k int)(ans int64){
slices.SortFunc(happiness,func(a, b int)int{return b - a })
for i, x :=range happiness[:k]{
if x <= i {
break
}
ans =int64(x - i)
}
return
}
func main(){
happiness :=[]int{1,2,3}
k :=2
fmt.Println(maximumHappinessSum(happiness, k))
}
Rust完整代码如下：
代码语言：javascript复制fn maximum_happiness_sum(happiness:&mutVec<i32>, k:usize)->i64{
happiness.sort_by(|a, b| b.cmp(a));
letmut ans:i64=0;
for(i,&x)in happiness.iter().take(k).enumerate(){
if x <= i asi32{
break;
}
ans = x asi64- i asi64;
}
ans
}
fnmain(){
letmut happiness=vec![1,2,3];
letk=2;
println!("{}",maximum_happiness_sum(&mut happiness, k));
}
