Leetcode Solution — 3075. Maximize Happiness of Selected Children

It is the biggest issue of distributing happiness to k children. You just have to sort and choose the one with the larger value. The time complexity is O(nlogn).

Korean blog : https://blog.naver.com/hongdevlife/223441084352

Problem

Find the value with the greatest sum when you divide the value by k Every time you give it away, it’s reduced by -1.

Input

• happiness : value array
• k: k children

Output

• the greatest sum

Solution

Intuition

The sum of distribution from the largest value is the greatest. There is a condition that decreases by one, and it is not necessary to reduce all arrays by one, but to reduce by the current ith when adding the value.

Approach

Combine the values in order of the largest by sorting. If the value is below zero, you can finish it because you don’t need to do it anymore.

Code

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; ++i) {
            int h = happiness[i] - i;
            if (h <= 0)
                break;
            ans += h;
        }
        return ans;
    }
};

Complexity

• Time complexity : O(nlogn)
• Space complexity : O(1)

a wrong reason

Wrong number 1 because it does not handle exceptions with h value of 0 or less

a retrospective

It’s a medium problem, but it was too easy.