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

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

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

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

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

 

示例 1：

输入：piles = [5,4,9], k = 2

输出：12

解释：可能的执行情景如下：

- 对第 2 堆石子执行移除操作，石子分布情况变成 [5,4,5] 。

- 对第 0 堆石子执行移除操作，石子分布情况变成 [3,4,5] 。

剩下石子的总数为 12 。

示例 2：

输入：piles = [4,3,6,7], k = 3

输出：12

解释：可能的执行情景如下：

- 对第 2 堆石子执行移除操作，石子分布情况变成 [4,3,3,7] 。

- 对第 3 堆石子执行移除操作，石子分布情况变成 [4,3,3,4] 。

- 对第 0 堆石子执行移除操作，石子分布情况变成 [2,3,3,4] 。

剩下石子的总数为 12 。

 

提示：

1 <= piles.length <= 105

1 <= piles[i] <= 104

1 <= k <= 105

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/remove-stones-to-minimize-the-total

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

public class RemoveStone {

    //元素可以改变顺序！！超时！！

    public int minStoneSum(int[] piles, int k) {

        for(int i = 0; i < k; i++){

            int max_number = 0;//当前轮最大的数值

            int max_number_index = 0;//当前值最大的下标

            for(int j = 0; j < piles.length; j++ ){

                if(piles[j] > max_number){

                    max_number_index = j;

                    max_number = piles[j];

                }

            }

            //去除当前值最的number的一半

            piles[max_number_index] -= (int) Math.floor(piles[max_number_index]/2);

        }

        int sum = 0;

        for(int i = 0; i < piles.length; i++){

            sum += piles[i];

        }

        return sum;

    }

    public int minStoneSum1(int[] piles, int k) {

        PriorityQueue<Integer> pq = new PriorityQueue<>((a,b) -> b-a);//构建大顶堆

        //将piles中元素入队

        for(int i = 0; i < piles.length; i++){

            pq.add(piles[i]);

        }

        //取堆顶元素减少一半并且重新放会堆中,循环k次

        //堆添加元素时间复杂度O(log N)

        for(int j = 0; j < k; j++){

            int top_que = pq.poll();

            top_que -= Math.floor(top_que/2.0);

            pq.add(top_que);

        }

        //计算和

        int sum = 0;

        for(Integer q: pq){

            sum += q;

        }

        return sum;

    }

    public int minStoneSum2(int[] piles, int k) {

        List<Integer> piles_list = new ArrayList<>();

        //将数组转换为list  超时！！

        for(int i = 0; i< piles.length;i++){

            piles_list.add(piles[i]);

        }

        //Collection.sort()采用的排序算法是一种改进的归并排序，归并算法的时间复杂度是O(nlog n)

        for(int j = 0; j < k; j++){

            piles_list.sort((a,b)->b-a);//先对list进行倒序排序

            piles_list.set(0, piles_list.get(0)-(int) Math.floor(piles_list.get(0)/2.0));//设置第一个值减少原来的一半

        }

        int sum =0;

        for(Integer q : piles_list){

            sum += q;

        }

        return sum;

    }

    public static void main(String[] args) {

        int[] piles = new int[]{4,3,6,7};

        int k = 3;

        RemoveStone rs = new RemoveStone();

        int result = rs.minStoneSum2(piles, k);

        System.out.println(result);

    }

}