Remove Stones to Minimize the Total

// Accepted solution for LeetCode #1962: Remove Stones to Minimize the Total
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;
    }
}

// Accepted solution for LeetCode #1962: Remove Stones to Minimize the Total
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) }

# Accepted solution for LeetCode #1962: Remove Stones to Minimize the Total
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)

// Accepted solution for LeetCode #1962: Remove Stones to Minimize the Total
/**
 * [1962] Remove Stones to Minimize the Total
 *
 * 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 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,<u>5</u>].
 * - Apply the operation on pile 0. The resulting piles are [<u>3</u>,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,<u>3</u>,7].
 * - Apply the operation on pile 3. The resulting piles are [4,3,3,<u>4</u>].
 * - Apply the operation on pile 0. The resulting piles are [<u>2</u>,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
 *
 */
pub struct Solution {}

// problem: https://leetcode.com/problems/remove-stones-to-minimize-the-total/
// discuss: https://leetcode.com/problems/remove-stones-to-minimize-the-total/discuss/?currentPage=1&orderBy=most_votes&query=

// submission codes start here

impl Solution {
    pub fn min_stone_sum(piles: Vec<i32>, k: i32) -> i32 {
        0
    }
}

// submission codes end

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    #[ignore]
    fn test_1962_example_1() {
        let piles = vec![5, 4, 9];
        let k = 2;

        let result = 12;

        assert_eq!(Solution::min_stone_sum(piles, k), result);
    }

    #[test]
    #[ignore]
    fn test_1962_example_2() {
        let piles = vec![4, 3, 6, 7];
        let k = 3;

        let result = 12;

        assert_eq!(Solution::min_stone_sum(piles, k), result);
    }
}

// Accepted solution for LeetCode #1962: Remove Stones to Minimize the Total
function minStoneSum(piles: number[], k: number): number {
    const pq = new MaxPriorityQueue<number>();
    for (const x of piles) {
        pq.enqueue(x);
    }
    while (k--) {
        pq.enqueue((pq.dequeue() + 1) >> 1);
    }
    return pq.toArray().reduce((a, b) => a + b, 0);
}