從最富有的一堆禮物中拿走

2558。從最富有的一堆禮物中拿走

難度：簡單

主題：陣列、堆疊（優先隊列）、模擬

您將獲得一個整數陣列禮物，表示各堆禮物的數量。每一秒，您都會執行以下操作：

• 選出禮物數量最多的那堆。
• 如果禮物數量超過上限，則選擇任一個。
• 留下一堆禮物數量的平方根的下限。剩下的禮物拿走吧。

回傳k秒後剩餘的禮物數量.

範例1：

• 輸入： 禮物 = [25,64,9,4,100], k = 4
• 輸出： 29
• 說明：禮物的領取方式如下：
  • 第一秒，最後一堆被選中，留下10份禮物。
  • 然後選擇第二堆，留下8份禮物。
  • 選完第一堆後，留下 5 份禮物。
  • 最後，最後一堆被再次選出，剩下3份禮物。
  • 最終剩餘禮物數量為[5,8,9,4,3]，所以剩餘禮物總數為29。

範例2：

• 輸入： 禮物 = [1,1,1,1], k = 4
• 輸出： 4
• 說明：這種情況下，無論你選擇哪一堆，每堆都必須留下 1 件禮物。
  • 也就是說，你不能帶走任何東西。
  • 所以，剩下的禮物總數是 4。

約束：

• 1 3
• 1 9
• 1 3

提示：

1. 如何追蹤陣列中最大的禮物
2. 求數字平方根的有效方法是什麼？
3. 你能不斷累加禮物的價值，同時確保它們按一定順序排列嗎？
4. 我們可以在這裡使用優先權佇列或堆嗎？

解：

我們可以利用最大堆（優先隊列），因為我們需要反覆挑選禮物數量最多的堆。最大堆將使我們能夠在恆定的時間內有效地訪問最大的堆，並在從堆中取出禮物後更新堆。

方法：

1. 使用最大堆：

   • 由於我們需要重複獲取最大數量禮物的堆，因此最大堆（優先隊列）是理想的選擇。在 PHP 中，我們可以使用 SplPriorityQueue，它是一個優先權佇列，預設用作最大堆。
   • 為了模擬最大堆，我們將插入禮物數量作為負值，因為 SplPriorityQueue 預設是最小堆。透過插入負值，最小的負值將代表最大的原始數。

2. 每秒處理：

   • 每一秒，從堆中彈出最多數量的禮物。
   • 拿走除該堆禮物數量平方根的下限以外的所有禮物。
   • 將修改後的堆推回堆中。

3. 終止：

   • 我們在 k 秒後或處理完所有秒後停止。

讓我們用 PHP 實作這個解：2558。從最富有的一堆禮物中拿走

<?php
/**
 * @param Integer[] $gifts
 * @param Integer $k
 * @return Integer
 */
function pickGifts($gifts, $k) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example usage:
$gifts1 = [25, 64, 9, 4, 100];
$k1 = 4;
echo pickGifts($gifts1, $k1) . "\n"; // Output: 29

$gifts2 = [1, 1, 1, 1];
$k2 = 4;
echo pickGifts($gifts2, $k2) . "\n"; // Output: 4
?>

解釋：

1. 堆初始化:

   • SplPriorityQueue 用於模擬最大堆。 insert 方法允許我們優先將元素推入堆中。

2. 處理最大的一堆：

   • 對於 k 次迭代，使用 extract 提取最大的一堆。
   • 留下的禮物數量計算為目前最大堆的平方根的下限，使用floor(sqrt(...))。
   • 減少的堆被重新插入到堆中。

3. 總結剩餘禮物：

   • 經過k次運算後，將堆中的所有元素提取出來並求和，得到剩餘禮物的總數。

4. 邊緣情況：

   • 如果禮物為空，則結果為0。
   • 如果 k 大於可能的運算元，演算法會妥善處理它。

時間複雜度：

• 堆操作（插入和提取）：每個堆操作（插入和提取）需要O(log n)，其中n 是堆的數量。
• 循環執行k 個操作：我們執行k 個操作，每個操作都涉及堆提取和插入，都需要O( log n).

因此，總時間複雜度為O(k log n)，其中n 是堆的數量，k 是秒數。

演練範例：

輸入：

<?php
/**
 * @param Integer[] $gifts
 * @param Integer $k
 * @return Integer
 */
function pickGifts($gifts, $k) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example usage:
$gifts1 = [25, 64, 9, 4, 100];
$k1 = 4;
echo pickGifts($gifts1, $k1) . "\n"; // Output: 29

$gifts2 = [1, 1, 1, 1];
$k2 = 4;
echo pickGifts($gifts2, $k2) . "\n"; // Output: 4
?>

1. 最初，優先權隊列有以下堆：[25, 64, 9, 4, 100]。
2. 1秒後：選擇100，留下10。剩餘禮物為：[25, 64, 9, 4, 10]。
3. 2秒後：選擇64，留下8。剩餘禮物為：[25,8,9,4,10]。
4. 3秒後：選25，剩下5。剩餘禮物為：[5,8,9,4,10]。
5. 4秒後：選10個，留下3個。剩下的禮物是：[5,8,9,4,3]。

剩餘禮物的總和為5 8 9 4 3 = 29。

這種方法使用最大堆有效地解決了問題，並且在給定的約束下表現良好。

聯絡連結

如果您發現本系列有幫助，請考慮在 GitHub 上給 存儲庫 一個星號或在您最喜歡的社交網絡上分享該帖子？ 。您的支持對我來說意義重大！

如果您想要更多類似的有用內容，請隨時關注我：

• 領英
• GitHub

以上是從最富有的一堆禮物中拿走的詳細內容。更多資訊請關注PHP中文網其他相關文章！