【贪心算法】将数组和减半的最小操作数

1.题目解析

2208. 将数组和减半的最少操作次数 - 力扣（LeetCode）

2.讲解算法原理

 使用当前数组中最大的数将它减半，，直到数组和减小到一半为止，从而快速达到目的

重点是找到最大数，可以采用大根堆快速达到目的

3.代码

class Solution {public int halveArray(int[] nums) {PriorityQueue<Double> heap=new PriorityQueue<>((a,b)->b.compareTo(a));//创建大根堆double sum=0;for(int x:nums){heap.offer((double)x);sum+=x;}int count=0;sum/=2.0;while(sum>0){double tmp=heap.poll()/2.0;sum-=tmp;count++;heap.offer(tmp);}return count;}
}

4.证明

证明方法：交换论证法