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^5
  • 1 <= piles[i] <= 10^4
  • 1 <= 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;
}

回目錄 Catalog