1962. 移除石子使总数最小 --力扣 --JAVA

题目

给你一个整数数组?piles?，数组?下标从 0 开始?，其中?piles[i]?表示第?i?堆石子中的石子数量。另给你一个整数?k?，请你执行下述操作?恰好?k?次：

• 选出任一石子堆?piles[i]?，并从中?移除?floor(piles[i] / 2)?颗石子。

注意：你可以对?同一堆?石子多次执行此操作。

返回执行?k?次操作后，剩下石子的?最小?总数。

floor(x)?为?小于?或?等于?x?的?最大?整数。（即，对?x?向下取整）。

解题思路

1. 每次对当前石子最多的堆进行操作；
2. 利用优先队列的倒序排列，可以便捷的获取最大的石子堆；
3. 统计操作前的石子总数；
4. 获取优先队列的首节点，移除对应石子，再将移除后的石子堆添加回队列，同时总数减去移除的石子。

代码展示

class Solution {
    public int minStoneSum(int[] piles, int k) {
        PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
        int sum = 0;
        for (int pile : piles){
            pq.add(pile);
            sum += pile;
        }
        while (--k >= 0){
            int pile = pq.poll();
            int temp = pile / 2;
            sum -= temp;
            pq.add(pile - temp);
        }
        return sum;
    }
}