3075. Maximize Happiness of Selected Children Medium

1/**
2 * [3075] Maximize Happiness of Selected Children
3 *
4 * You are given an array happiness of length n, and a positive integer k.
5 * 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.
6 * 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.
7 * Return the maximum sum of the happiness values of the selected children you can achieve by selecting k children.
8 *  
9 * <strong class="example">Example 1:
10 * 
11 * Input: happiness = [1,2,3], k = 2
12 * Output: 4
13 * Explanation: We can pick 2 children in the following way:
14 * - Pick the child with the happiness value == 3. The happiness value of the remaining children becomes [0,1].
15 * - Pick the child with the happiness value == 1. The happiness value of the remaining child becomes [0]. Note that the happiness value cannot become less than 0.
16 * The sum of the happiness values of the selected children is 3 + 1 = 4.
17 * 
18 * <strong class="example">Example 2:
19 * 
20 * Input: happiness = [1,1,1,1], k = 2
21 * Output: 1
22 * Explanation: We can pick 2 children in the following way:
23 * - Pick any child with the happiness value == 1. The happiness value of the remaining children becomes [0,0,0].
24 * - Pick the child with the happiness value == 0. The happiness value of the remaining child becomes [0,0].
25 * The sum of the happiness values of the selected children is 1 + 0 = 1.
26 * 
27 * <strong class="example">Example 3:
28 * 
29 * Input: happiness = [2,3,4,5], k = 1
30 * Output: 5
31 * Explanation: We can pick 1 child in the following way:
32 * - Pick the child with the happiness value == 5. The happiness value of the remaining children becomes [1,2,3].
33 * The sum of the happiness values of the selected children is 5.
34 * 
35 *  
36 * Constraints:
37 * 
38 * 	1 <= n == happiness.length <= 2 * 10^5
39 * 	1 <= happiness[i] <= 10^8
40 * 	1 <= k <= n
41 * 
42 */
43pub struct Solution {}
44
45// problem: https://leetcode.com/problems/maximize-happiness-of-selected-children/
46// discuss: https://leetcode.com/problems/maximize-happiness-of-selected-children/discuss/?currentPage=1&orderBy=most_votes&query=
47
48// submission codes start here
49
50impl Solution {
51    pub fn maximum_happiness_sum(happiness: Vec<i32>, k: i32) -> i64 {
52        
53    }
54}
55
56// submission codes end
57
58#[cfg(test)]
59mod tests {
60    use super::*;
61
62    #[test]
63    fn test_3075() {
64    }
65}
66