主題
題目連結：
題目意譯：
你被給定一個整數陣列 gifts 代表著不同堆中的禮物數量。每一秒，你將會做以下的事情：
選出有著最多禮物的那一堆；
如果存在著多於一個有最多禮物的禮物堆，則任選一個；
留下該堆中禮物數的平方根之向下取整之值在禮物堆中，並拿走剩下的禮物。
回傳 k 秒後剩餘禮物數。
限制：
1 ≦ gifts.length ≦ 10 ^ 3
1 ≦ gifts[i] ≦ 10 ^ 9
1 ≦ k ≦ 10 ^ 3
範例測資：
範例 1：
輸入： gifts = [25,64,9,4,100], k = 4
輸出： 29
解釋：
你將按照下列方式拿走禮物：
- 在第一秒中，你將選擇最後一堆並留下 10 個禮物。
- 接著，你將選擇第二堆並留下 8 個禮物。
- 之後，你將選擇第一堆並留下 5 個禮物。
- 最後，你將再次選擇最後一堆並留下 3 個禮物。
最終剩餘的禮物為 [5,8,9,4,3]，所以總計剩餘禮物數為 29。
範例 2：
輸入： gifts = [1,1,1,1], k = 4
輸出： 4
解釋：
在此例中，無論你選哪一堆，你在每一堆都必須留下一個禮物。
也就是說，你沒辦法完全拿走任何一堆禮物。
所以，總剩餘禮物數為 4。
解題思維：
因為 gifts 長度（稱其為 n）最長也只有 10 ^ 3，因此時間複雜度為 O(kn) 的作法在本題也是可行的。也就是說為 k 秒中的每一秒，找到陣列 gifts 中當前最大值的位置並根據題意更改數值（假設原本是 x，則之後應為 floor(sqrt(x))）。
最後再加總剩下的禮物數即可。
而當然，我們可以做得更好。為了在每一秒中找到當下的最大值，我們可以使用優先佇列（Priority Queue）來維護。一開始，我們將會把 gifts 中所有數字丟進優先佇列中。然後每一秒就從佇列中取出最大值並根據題意更改數值再塞回優先佇列中。
一樣最後再一一從優先佇列中取出每一堆剩下的禮物數並加總即可。時間複雜度為 O((n + k) × log(n))。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
