Last Updated on 2022-12-30 by Clay
題目
You are given a 0-indexed integer array piles, where piles[i] represents the number of stones in the ith pile, and an integer k. You should apply the following operation exactly k times:
- Choose any
piles[i]and removefloor(piles[i] / 2)stones from it.
Notice that you can apply the operation on the same pile more than once.
Return the minimum possible total number of stones remaining after applying the k operations.
floor(x) is the greatest integer that is smaller than or equal to x (i.e., rounds x down).
Example 1:
Input: piles = [5,4,9], k = 2 Output: 12 Explanation: Steps of a possible scenario are: - Apply the operation on pile 2. The resulting piles are [5,4,5]. - Apply the operation on pile 0. The resulting piles are [3,4,5]. The total number of stones in [3,4,5] is 12.
Example 2:
Input: piles = [4,3,6,7], k = 3 Output: 12 Explanation: Steps of a possible scenario are: - Apply the operation on pile 2. The resulting piles are [4,3,3,7]. - Apply the operation on pile 3. The resulting piles are [4,3,3,4]. - Apply the operation on pile 0. The resulting piles are [2,3,3,4]. The total number of stones in [2,3,3,4] is 12.
Constraints:
1 <= piles.length <= 1051 <= piles[i] <= 1041 <= k <= 105
解題思路
優先權佇列（Priority Queue）
首先先把 piles 中的所有值加總，得到當前所有的石頭總數；接著使用優先權佇列（priority queue）來儲存每個 pile 中石頭的數量。如此一來，我們就能直接取得當前最多石頭的 pile，倒去一半，再把剩餘的部分重新儲存回優先權佇列中。
同時，我們也要把倒去的一半石頭數量，從 piles 加總的值中減去。這樣一來當我們能操作次數 k 值歸零後，我們就能馬上得到答案。
優先權佇列（Priority Queue） 複雜度
| Time Complexity | O(n) |
| Space Complexity | O(n) |
C++ 範例程式碼
class Solution {
public:
int minStoneSum(vector<int>& piles, int k) {
// Init
int stoneSum = accumulate(piles.begin(), piles.end(), 0);
priority_queue<int> pq(piles.begin(), piles.end());
// Remove stones
while (pq.top() != 0 && k > 0) {
int removeStone = floor(pq.top() / 2);
int remainStone = pq.top() - removeStone;
pq.pop();
pq.push(remainStone);
stoneSum -= removeStone;
--k;
}
return stoneSum;
}
};