Question

1962. Remove Stones to Minimize the Total

中文文档

Description

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 <= 105
• 1 <= piles[i] <= 104
• 1 <= k <= 105

Solutions

Solution 1: Greedy + Priority Queue (Max Heap)

According to the problem description, in order to minimize the total number of remaining stones, we need to remove as many stones as possible from the stone piles. Therefore, we should always choose the pile with the most stones for removal.

We create a priority queue (max heap) $pq$ to store the number of stones in each pile. Initially, we add the number of stones in all piles to the priority queue.

Next, we perform $k$ operations. In each operation, we take out the top element $x$ of the priority queue, halve $x$, and then add it back to the priority queue.

After performing $k$ operations, the sum of all elements in the priority queue is the answer.

The time complexity is $O(n + k \times \log n)$, and the space complexity is $O(n)$. Where $n$ is the length of the array piles.

class Solution:
  def minStoneSum(self, piles: List[int], k: int) -> int:
    pq = [-x for x in piles]
    heapify(pq)
    for _ in range(k):
      heapreplace(pq, pq[0] // 2)
    return -sum(pq)

class Solution {
  public int minStoneSum(int[] piles, int k) {
    PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> b - a);
    for (int x : piles) {
      pq.offer(x);
    }
    while (k-- > 0) {
      int x = pq.poll();
      pq.offer(x - x / 2);
    }
    int ans = 0;
    while (!pq.isEmpty()) {
      ans += pq.poll();
    }
    return ans;
  }
}

class Solution {
public:
  int minStoneSum(vector<int>& piles, int k) {
    priority_queue<int> pq;
    for (int x : piles) {
      pq.push(x);
    }
    while (k--) {
      int x = pq.top();
      pq.pop();
      pq.push(x - x / 2);
    }
    int ans = 0;
    while (!pq.empty()) {
      ans += pq.top();
      pq.pop();
    }
    return ans;
  }
};

func minStoneSum(piles []int, k int) (ans int) {
  pq := &hp{piles}
  heap.Init(pq)
  for ; k > 0; k-- {
    x := pq.pop()
    pq.push(x - x/2)
  }
  for pq.Len() > 0 {
    ans += pq.pop()
  }
  return
}

type hp struct{ sort.IntSlice }

func (h hp) Less(i, j int) bool { return h.IntSlice[i] > h.IntSlice[j] }
func (h *hp) Push(v any)    { h.IntSlice = append(h.IntSlice, v.(int)) }
func (h *hp) Pop() any {
  a := h.IntSlice
  v := a[len(a)-1]
  h.IntSlice = a[:len(a)-1]
  return v
}
func (h *hp) push(v int) { heap.Push(h, v) }
func (h *hp) pop() int   { return heap.Pop(h).(int) }

function minStoneSum(piles: number[], k: number): number {
  const pq = new MaxPriorityQueue();
  for (const x of piles) {
    pq.enqueue(x);
  }
  while (k--) {
    const x = pq.dequeue().element;
    pq.enqueue(x - ((x / 2) | 0));
  }
  let ans = 0;
  while (pq.size()) {
    ans += pq.dequeue().element;
  }
  return ans;
}