You are given an array numsof positive integers. In one operation, you can choose any number from numsand reduce it to exactly half the number. (Note that you may choose this reduced number in future operations.)

Return the minimum number of operations to reduce the sum of numsby at least half.

(相关资料图)

Example 1:

Input: nums = [5,19,8,1]

Output: 3

Explanation: The initial sum of nums is equal to 5 + 19 + 8 + 1 = 33. 

The following is one of the ways to reduce the sum by at least half: 

Pick the number 19 and reduce it to 9.5.

Pick the number 9.5 and reduce it to 4.75.

Pick the number 8 and reduce it to 4. 

The final array is [5, 4.75, 4, 1] with a total sum of 5 + 4.75 + 4 + 1 = 14.75. 

The sum of nums has been reduced by 33 - 14.75 = 18.25, 

which is at least half of the initial sum, 18.25 >= 33/2 = 16.5. 

Overall, 3 operations were used so we return 3. 

It can be shown that we cannot reduce the sum by at least half in less than 3 operations.

Example 2:

Input: nums = [3,8,20]

Output: 3

Explanation: The initial sum of nums is equal to 3 + 8 + 20 = 31. 

The following is one of the ways to reduce the sum by at least half:

Pick the number 20 and reduce it to 10.

Pick the number 10 and reduce it to 5.

Pick the number 3 and reduce it to 1.5. 

The final array is [1.5, 8, 5] with a total sum of 1.5 + 8 + 5 = 14.5. 

The sum of nums has been reduced by 31 - 14.5 = 16.5, 

which is at least half of the initial sum, 16.5 >= 31/2 = 15.5. 

Overall, 3 operations were used so we return 3. 

It can be shown that we cannot reduce the sum by at least half in less than 3 operations.

Constraints:

1 <= nums.length <= 105

1 <= nums[i] <= 107

如果将目前的总和降为一半以上，肯定是将最大的元素降为1半是速度最快的，所以就要每次判断哪个是最大的元素，每次都要最值元素，优先考虑优先队列，使用reverse order 的规则。

然后while 循环即可。

要是难题也能这么快做出来就好了。。。。。。。。

Runtime: 244 ms, faster than 62.55% of Java online submissions for Minimum Operations to Halve Array Sum.

Memory Usage: 59.3 MB, less than 56.37% of Java online submissions for Minimum Operations to Halve Array Sum.

标签：