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

2023-12-23 18:24:10

题目

给你一个整数数组?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;
    }
}

文章来源:https://blog.csdn.net/qq_45794129/article/details/135167305
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。