Remove Stones to Minimize the Total
Problem
On each of k operations, choose a pile and remove floor(pile/2) stones. Minimize the final total.
piles = [5,4,9], k = 212import heapq
def min_stone_sum(piles, k):
heap = [-p for p in piles]
heapq.heapify(heap)
for _ in range(k):
x = -heapq.heappop(heap)
x -= x // 2
heapq.heappush(heap, -x)
return -sum(heap)function minStoneSum(piles, k) {
// simple sort-based heap simulation for clarity
piles = piles.slice();
for (let i = 0; i < k; i++) {
piles.sort((a, b) => b - a);
piles[0] -= Math.floor(piles[0] / 2);
}
return piles.reduce((a, b) => a + b, 0);
}class Solution {
public int minStoneSum(int[] piles, int k) {
PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
for (int p : piles) pq.offer(p);
for (int i = 0; i < k; i++) {
int x = pq.poll();
x -= x / 2;
pq.offer(x);
}
int sum = 0; for (int x : pq) sum += x; return sum;
}
}int minStoneSum(vector<int>& piles, int k) {
priority_queue<int> pq(piles.begin(), piles.end());
for (int i = 0; i < k; i++) {
int x = pq.top(); pq.pop();
x -= x / 2;
pq.push(x);
}
int sum = 0; while (!pq.empty()) { sum += pq.top(); pq.pop(); } return sum;
}Explanation
To remove as many stones as possible, you should always halve the biggest pile available. Removing half of a large pile takes away more stones than halving any smaller pile, so it is always the best greedy choice. A max-heap keeps the largest pile at your fingertips.
We push all piles into a max-heap. Then we repeat k times: pop the largest pile x, remove floor(x / 2) stones (so the pile becomes x - x // 2, which is ceil(x / 2)), and push the smaller pile back in.
After all k operations, we simply sum whatever remains in the heap and return that total.
Example: piles = [5, 4, 9], k = 2. The largest is 9; halving gives 5, so piles become [5, 4, 5]. The largest is now 5; halving gives 3, so piles become [3, 4, 5]... summing the leftovers gives 5 + 4 + 3 = 12.
Greedily attacking the tallest pile each round guarantees the maximum number of stones removed within the k moves, which is exactly what minimizes the final total.