题目名称

给你一个正整数数组 nums 。每一次操作中，你可以从 nums 中选择 任意 一个数并将它减小到 恰好 一半。（注意，在后续操作中你可以对减半过的数继续执行操作）

请你返回将 nums 数组和 至少 减少一半的 最少 操作数

示例

输入：nums = [5,19,8,1]
输出：3
解释：初始 nums 的和为 5 + 19 + 8 + 1 = 33 。
以下是将数组和减少至少一半的一种方法：
选择数字 19 并减小为 9.5 。
选择数字 9.5 并减小为 4.75 。
选择数字 8 并减小为 4 。
最终数组为 [5, 4.75, 4, 1] ，和为 5 + 4.75 + 4 + 1 = 14.75 。
nums 的和减小了 33 - 14.75 = 18.25 ，减小的部分超过了初始数组和的一半，18.25 >= 33/2 = 16.5 。
我们需要 3 个操作实现题目要求，所以返回 3 。
可以证明，无法通过少于 3 个操作使数组和减少至少一半。

题解

思路就是每次将最大的数减半，然后看得到的结果是否使数组的和减半

比较麻烦的是如何取得最大的数

答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
var halveArray = function(nums) {
    let q=new MaxPriorityQueue();
    nums.forEach(v=>q.enqueue(v));
    let sum=nums.reduce((p,c)=>p+c,0),t=0,num=0;
    while(t<sum/2){
        num++;
        t+=(q.front().element/2);
        q.enqueue(q.dequeue().element/2);
    }
    return num;
};

// 我的算法，但是超时了，思路是没问题的
/**
 * @param {number[]} nums
 * @return {number}
 */
 var halveArray = function(nums) {
  nums = nums.sort((a, b) => b-a)
  let total = nums.reduce((total, item) => total += item, 0), step = 0, reduce = total, avage = total / nums.length / 2
  nums = nums.filter(item => item >= avage)
  while(reduce >= total / 2) {
    let item = nums.shift() / 2
    reduce -= item
    step++
    if(item > avage) {
      for(let i = 0; i < nums.length; i++) {
        if(item > nums[i]) {
          nums.splice(i, 0, item)
          break;
        }
      }
    }
  }
  return step
};