Formatted question description: https://leetcode.ca/all/1962.html

1962. Remove Stones to Minimize the Total

Level

Medium

Description

You are given a 0-indexed integer array piles, where piles[i] represents the number of stones in the i-th 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 smaller8* 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 3. The resulting piles are [4,3,3,7].
  • Apply the operation on pile 4. 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

Solution

Use a greedy approach. To make the total number of stones remaining minimum, each time remove the most stones as possible. Therefore, each time select the pile with the maximum number of stones, and remove half of the stones from the pile. Use a priority queue to maintain the piles for each operation. Finally, return the sum of the remaining stones.

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

All Problems

All Solutions