将数组和减半的最少操作次数

难度: Medium

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

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

示例 1：

输入：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 个操作使数组和减少至少一半。

示例 2：

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

提示：

1 <= nums.length <= 10⁵
1 <= nums[i] <= 10⁷

Submission

运行时间: 184 ms

内存: 27.2 MB

class Solution:
    def halveArray(self, nums: List[int]) -> int:
        total = sum(nums)
        nums.sort()
        deq = deque()
        deq.append(nums[-1]/2)
        ans = 1
        sub = nums[-1]/2
        nums.pop()
        while sub < total/2 and nums:
            if deq[0]> nums[-1]:

                cur = deq.popleft()
            else:
                cur = nums.pop()
            sub += cur/2
            ans += 1
            deq.append(cur/2)
        return ans

Explain

题解采用贪心策略，优先选择能对总和减少最大影响的数进行操作。首先计算数组的初始总和。数组进行排序后，从最大的数开始，每次选择当前最大的数，将其减半并累加操作次数，直到减半的累计值达到或超过原数组总和的一半。此外，使用一个双端队列(deque)来存储每次操作后生成的新数值，保证每次都能从当前可选的数中挑选最大的进行操作。

时间复杂度: O(n log n)

空间复杂度: O(n)

class Solution:
    def halveArray(self, nums: List[int]) -> int:
        total = sum(nums)  # 计算初始总和
        nums.sort()  # 对数组进行排序
        deq = deque()  # 创建双端队列存储减半后的数值
        deq.append(nums[-1]/2)  # 将最大元素减半后加入队列
        ans = 1  # 操作计数
        sub = nums[-1]/2  # 减少的总和
        nums.pop()  # 移除已操作的最大元素
        while sub < total/2 and nums:  # 直到减少的总和达到原总和的一半
            if deq[0] > nums[-1]:  # 从队列和数组中选择当前最大的数
                cur = deq.popleft()
            else:
                cur = nums.pop()
            sub += cur/2  # 累加减半的数值到减少的总和
            ans += 1  # 增加操作次数
            deq.append(cur/2)  # 将操作后的数值加入队列
        return ans  # 返回总操作次数

Explore

在题解中，每次操作后将新的数值加入双端队列时，新数值总是原数值的一半，因此通常比队列中已存在的元素要小。为保持队列的顺序，只需将新数值添加到队列的末端。此外，每次操作选择最大值时，比较队列首部和数组尾部的元素，这样可以保证从当前所有可选的数中选择最大的。

如果数组中包含多个相同的最大值，题解策略会从这些最大值中任选一个进行减半操作，因为它们都提供相同的减少总和的贡献。选择哪一个并不影响操作次数，因为每个数减半后的值相同，对总体目标的贡献一致。因此，即使选择不同的相同最大值进行操作，最终的操作次数也不会受到影响。

选择每次只将一个数减半是由于这样可以更精确地控制每次操作对总和的影响，保证每次操作都能最大限度地减少总和。同时操作多个数虽然看起来效率更高，但难以保证每次操作都是最优的，可能会导致需要更多的操作次数才能达到目标。此外，单个操作简化了问题的处理和队列的管理。

在这种情况下，实际上题解的设计意味着数组不可能在减少总和未达到目标时就变空。每次操作后，操作的数值会被减半后再次添加到队列中，所以队列和数组中总是有元素可用，直到减半的总和达到目标。因此，按照设计，总会有足够的数值可以操作，直到满足条件。