文章目錄

• • 1. 題目
  • 2. 解題

1. 題目

給你一個整數(shù)數(shù)組 piles ，數(shù)組 下標(biāo)從 0 開始 ，其中 piles[i] 表示第 i 堆石子中的石子數(shù)量。
另給你一個整數(shù) k ，請你執(zhí)行下述操作 恰好 k 次：

選出任一石子堆 piles[i] ，并從中 移除 floor(piles[i] / 2) 顆石子。
注意：你可以對 同一堆 石子多次執(zhí)行此操作。

返回執(zhí)行 k 次操作后，剩下石子的 最小 總數(shù)。

floor(x) 為 小于 或 等于 x 的 最大 整數(shù)。（即，對 x 向下取整）。

示例 1： 輸入：piles = [5,4,9], k = 2 輸出：12 解釋：可能的執(zhí)行情景如下： - 對第 2 堆石子執(zhí)行移除操作，石子分布情況變成 [5,4,5] 。 - 對第 0 堆石子執(zhí)行移除操作，石子分布情況變成 [3,4,5] 。 剩下石子的總數(shù)為 12 。示例 2： 輸入：piles = [4,3,6,7], k = 3 輸出：12 解釋：可能的執(zhí)行情景如下： - 對第 2 堆石子執(zhí)行移除操作，石子分布情況變成 [4,3,3,7] 。 - 對第 3 堆石子執(zhí)行移除操作，石子分布情況變成 [4,3,3,4] 。 - 對第 0 堆石子執(zhí)行移除操作，石子分布情況變成 [2,3,3,4] 。 剩下石子的總數(shù)為 12 。提示： 1 <= piles.length <= 10^5 1 <= piles[i] <= 10^4 1 <= k <= 10^5

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/remove-stones-to-minimize-the-total
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處。

2. 解題

• 優(yōu)先隊列，總是拿剩余最多的一堆

class Solution { public:int minStoneSum(vector<int>& piles, int k) {priority_queue<int> q(piles.begin(), piles.end());while(k--){int w = q.top();if(w == 1)return q.size();q.pop();q.push(w-w/2);}int ans = 0;while(!q.empty()){ans += q.top();q.pop();}return ans;} };

524 ms 96.5 MB C++

---

我的CSDN博客地址 https://michael.blog.csdn.net/

長按或掃碼關(guān)注我的公眾號（Michael阿明），一起加油、一起學(xué)習(xí)進(jìn)步！

總結(jié)

以上是生活随笔為你收集整理的LeetCode 1962. 移除石子使总数最小（优先队列）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。