Maximize Happiness of Selected Children
You are given an array happiness of length n, and a positive integer k.
There are n children standing in a queue, where the i^th child has happiness value happiness[i]. You want to select k children from these n children in k turns.
In each turn, when you select a child, the happiness value of all the children that have not been selected till now decreases by 1. Note that the happiness value cannot become negative and gets decremented only if it is positive.
Return the maximum sum of the happiness values of the selected children you can achieve by selecting k children.
Example 1
Input
happiness = [1,2,3], k = 2Output
4Selecting the child with happiness 3 first leaves remaining happiness values [0, 1], then selecting the child with happiness 1 gives a total of 3 + 1 = 4.
Example 2
Input
happiness = [1,1,1,1], k = 2Output
1Selecting any child with happiness 1 first makes all remaining children have happiness 0, so the best total is 1 + 0 = 1.
Constraints
- 1 <= n == happiness.length <= 2 * 10^5
- 1 <= happiness[i] <= 10^8
- 1 <= k <= n