leetcode 3075（排序+贪心）

3075: 幸福值最大化的选择方案

为什么一定要按“从大到小”的顺序选？

• 如果值都很大，大家减完 1 都还是正数，顺序不影响；

• 反之，因为小的会减为 0，晚点选它没损失；但大的如果晚点选，就会被白白减去 1。

本质上，由于存在 max(0,...) 这个 “截断” 机制，越小的值越容易触发 “保底 0”。为了保护总和，我们应该优先榨取大值的剩余价值，让那些迟早要变成 0的小值去承担减量。

每个孩子被选中时，其贡献是 max(0, 初始值 - 已经过去的轮数)；

只能选k个，优先选择较大的。

class Solution { public: long long maximumHappinessSum(vector<int>& happiness, int k) { long long ans=0; int m=0; sort(happiness.begin(),happiness.end()); for(int i=happiness.size()-1;i>=0;i--){ ans+=happiness[i]; m++; if(m==k) break; if(i-1>=0 && happiness[i-1]>0) happiness[i-1]=max(0,happiness[i-1]-m); } return ans; } };