maximize-happiness-of-selected-children

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

You are given an array <code>happiness</code> of length <code>n</code>, and a positive integer <code>k</code>.

There are <code>n</code> children standing in a queue, where the <code>ith</code> child has happiness value <code>happiness[i]</code>. You want to select <code>k</code> children from these <code>n</code> children in <code>k</code> 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 <code>1</code>. 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 <code>k</code> children.

&nbsp;
Example 1:

<pre>
Input: happiness = [1,2,3], k = 2
Output: 4
Explanation: We can pick 2 children in the following way:
- Pick the child with the happiness value == 3. The happiness value of the remaining children becomes [0,1].
- 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.
The sum of the happiness values of the selected children is 3 + 1 = 4.
</pre>

Example 2:

<pre>
Input: happiness = [1,1,1,1], k = 2
Output: 1
Explanation: We can pick 2 children in the following way:
- Pick any child with the happiness value == 1. The happiness value of the remaining children becomes [0,0,0].
- Pick the child with the happiness value == 0. The happiness value of the remaining child becomes [0,0].
The sum of the happiness values of the selected children is 1 + 0 = 1.
</pre>

Example 3:

<pre>
Input: happiness = [2,3,4,5], k = 1
Output: 5
Explanation: We can pick 1 child in the following way:
- Pick the child with the happiness value == 5. The happiness value of the remaining children becomes [1,2,3].
The sum of the happiness values of the selected children is 5.
</pre>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= n == happiness.length &lt;= 2 * 105</code></li>
	<li><code>1 &lt;= happiness[i] &lt;= 108</code></li>
	<li><code>1 &lt;= k &lt;= n</code></li>
</ul>

maximumHappinessSum

Maximize Happiness of Selected Children

Maximum Candies Allocated to K Children

maximum-candies-allocated-to-k-children

每个小孩最多能分到多少糖果

Greedy

Array

Sorting

给你一个长度为 <code>n</code> 的数组 <code>happiness</code> ，以及一个 正整数 <code>k</code> 。

<code>n</code> 个孩子站成一队，其中第 <code>i</code> 个孩子的 幸福值 是 <code>happiness[i]</code> 。你计划组织 <code>k</code> 轮筛选从这 <code>n</code> 个孩子中选出 <code>k</code> 个孩子。

在每一轮选择一个孩子时，所有 尚未 被选中的孩子的 幸福值 将减少 <code>1</code> 。注意，幸福值 不能 变成负数，且只有在它是正数的情况下才会减少。

选择 <code>k</code> 个孩子，并使你选中的孩子幸福值之和最大，返回你能够得到的 最大值 。

&nbsp;

示例 1：

<pre>
输入：happiness = [1,2,3], k = 2
输出：4
解释：按以下方式选择 2 个孩子：
- 选择幸福值为 3 的孩子。剩余孩子的幸福值变为 [0,1] 。
- 选择幸福值为 1 的孩子。剩余孩子的幸福值变为 [0] 。注意幸福值不能小于 0 。
所选孩子的幸福值之和为 3 + 1 = 4 。
</pre>

示例 2：

<pre>
输入：happiness = [1,1,1,1], k = 2
输出：1
解释：按以下方式选择 2 个孩子：
- 选择幸福值为 1 的任意一个孩子。剩余孩子的幸福值变为 [0,0,0] 。
- 选择幸福值为 0 的孩子。剩余孩子的幸福值变为 [0,0] 。
所选孩子的幸福值之和为 1 + 0 = 1 。
</pre>

示例 3：

<pre>
输入：happiness = [2,3,4,5], k = 1
输出：5
解释：按以下方式选择 1 个孩子：
- 选择幸福值为 5 的孩子。剩余孩子的幸福值变为 [1,2,3] 。
所选孩子的幸福值之和为 5 。
</pre>

&nbsp;

提示：

<ul>
	<li><code>1 &lt;= n == happiness.length &lt;= 2 * 105</code></li>
	<li><code>1 &lt;= happiness[i] &lt;= 108</code></li>
	<li><code>1 &lt;= k &lt;= n</code></li>
</ul>