take-gifts-from-the-richest-pile

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 integer array <code>gifts</code> denoting the number of gifts in various piles. Every second, you do the following:

<ul>
	<li>Choose the pile with the maximum number of gifts.</li>
	<li>If there is more than one pile with the maximum number of gifts, choose any.</li>
	<li>Reduce the number of gifts in the pile to the floor of the square root of the original number of gifts in the pile.</li>
</ul>

Return the number of gifts remaining after <code>k</code> seconds.

&nbsp;
Example 1:

<pre>
Input: gifts = [25,64,9,4,100], k = 4
Output: 29
Explanation: 
The gifts are taken in the following way:
- In the first second, the last pile is chosen and 10 gifts are left behind.
- Then the second pile is chosen and 8 gifts are left behind.
- After that the first pile is chosen and 5 gifts are left behind.
- Finally, the last pile is chosen again and 3 gifts are left behind.
The final remaining gifts are [5,8,9,4,3], so the total number of gifts remaining is 29.
</pre>

Example 2:

<pre>
Input: gifts = [1,1,1,1], k = 4
Output: 4
Explanation: 
In this case, regardless which pile you choose, you have to leave behind 1 gift in each pile. 
That is, you can&#39;t take any pile with you. 
So, the total gifts remaining are 4.
</pre>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= gifts.length &lt;= 103</code></li>
	<li><code>1 &lt;= gifts[i] &lt;= 109</code></li>
	<li><code>1 &lt;= k &lt;= 103</code></li>
</ul>

pickGifts

Take Gifts From the Richest Pile

Remove Stones to Minimize the Total

remove-stones-to-minimize-the-total

移除石子使总数最小

Array

Simulation

Heap (Priority Queue)

给你一个整数数组 <code>gifts</code> ，表示各堆礼物的数量。每一秒，你需要执行以下操作：

<ul>
	<li>选择礼物数量最多的那一堆。</li>
	<li>如果不止一堆都符合礼物数量最多，从中选择任一堆即可。</li>
	<li>将堆中的礼物数量减少到堆中原来礼物数量的平方根，向下取整。</li>
</ul>

返回在 <code>k</code> 秒后剩下的礼物数量。

&nbsp;

示例 1：

<pre>
输入：gifts = [25,64,9,4,100], k = 4
输出：29
解释： 
按下述方式取走礼物：
- 在第一秒，选中最后一堆，剩下 10 个礼物。
- 接着第二秒选中第二堆礼物，剩下 8 个礼物。
- 然后选中第一堆礼物，剩下 5 个礼物。
- 最后，再次选中最后一堆礼物，剩下 3 个礼物。
最后剩下的礼物数量分别是 [5,8,9,4,3] ，所以，剩下礼物的总数量是 29 。
</pre>

示例 2：

<pre>
输入：gifts = [1,1,1,1], k = 4
输出：4
解释：
在本例中，不管选中哪一堆礼物，都必须剩下 1 个礼物。 
也就是说，你无法获取任一堆中的礼物。 
所以，剩下礼物的总数量是 4 。
</pre>

&nbsp;

提示：

<ul>
	<li><code>1 &lt;= gifts.length &lt;= 103</code></li>
	<li><code>1 &lt;= gifts[i] &lt;= 109</code></li>
	<li><code>1 &lt;= k &lt;= 103</code></li>
</ul>