leetcode 3075

题目

例子

思路

孩子的幸福值最低也是0，所以选择最大的值，被选孩子的幸福值最高。需要使用排序算法

代码实现

class Solution {
public:
    long long maximumHappinessSum(vector<int>& happiness, int k) {

        //升序
        sort(happiness.begin(), happiness.end(), greater<int>());
        
        long long ans = 0;
        
        for(int i=0, j=0; i<k; i++){
            if(j < happiness.size()){
                if(happiness[j]-i <= 0){
                    return ans;
                }else{
                    ans += happiness[j] -i;
                    j++;
                }
            }
        }
        return ans;      
    }
};

执行时间是177ms

class Solution {
public:
    long long maximumHappinessSum(vector<int>& happiness, int k) {

        //升序
        sort(happiness.begin(), happiness.end(), greater<int>());
        
        long long ans = 0;
        
        for(int i=0; i<k && happiness[i] > i; i++){
            ans += happiness[i] -i;
        }
        return ans;      
    }
};

执行时间是151ms