1962. Remove Stones to Minimize the Total
- Hardness: \(\color{orange}\textsf{Medium}\)
- Ralated Topics:
Array、Heap (Priority Queue)
一、題目
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 remove floor(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 <= 10^51 <= piles[i] <= 10^41 <= k <= 10^5
二、分析
- 用
greedy的思維來思考這一題，每次動作會減去piles[i]一半的石頭，要使k次後石頭總數最小，那必定是每次都要選在石頭最多的堆來動作。 - 由於石頭最多的堆是動態更新的，也就是說不能單純用
sort來解決。舉例來說，每堆的石頭有非常多，那它執行許多次動作仍可能是最多的。 - 利用
max heap將最多石頭的堆重覆推到top，反覆動作k次即可解。
三、解題
1. Heap (Priority Queue)
- Time complexity: \(O(k\log n+n)\)
- Space complexity: \(O(n)\)
int minStoneSum(vector<int>& piles, int k) {
priority_queue<int> pq;
int res = 0;
for (const auto& pile : piles) {
pq.push(pile); // 先將所有堆都推到 priority queue 上
res += pile; // 順便將原本的石頭總數算出來
}
while (k--) {
int curr = pq.top(); pq.pop();
int loss = curr >> 1; // 當下的 max heap 的堆頂除於 2 即為當下可以一次取到最多的石頭
pq.push(curr - loss); // 將取完的堆放回 priority queue 上
res -= loss; // 將總數減掉拿掉的石頭
}
return res;
}