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

题目描述

给你一个正整数数组 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 = 16.5 。我们需要 3 个操作实现题目要求，所以返回 3 。可以证明，无法通过少于 3 个操作使数组和减少至少一半。

提示：

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

解法一：优先队列

 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


type PriorityQueue struct {
    sort.Float64Slice
}

func (pq *PriorityQueue) Less(i, j int) bool {
    return pq.Float64Slice.Less(j, i)
}

func (pq *PriorityQueue) Push(x interface{}) {
    pq.Float64Slice = append(pq.Float64Slice, x.(float64))
}

func (pq *PriorityQueue) Pop() interface{} {
    a := pq.Float64Slice
    ret := a[len(a)-1]
    pq.Float64Slice = a[:len(a)-1]
    return ret
}

func halveArray(nums []int) int {
    sum, pq := 0, &PriorityQueue{}
    for _, num := range nums {
        sum += num
        heap.Push(pq, float64(num))
    }
    half := -float64(sum) / 2.0
    ans := 0
    for math.Signbit(half) {
        top := heap.Pop(pq).(float64) / 2.0
        half += top
        heap.Push(pq, top)
        ans++
    }
    return ans
}

官方题解如下：

 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
38
39
40
41


type PriorityQueue []float64

func (pq PriorityQueue) Len() int {
    return len(pq)
}

func (pq PriorityQueue) Less(i, j int) bool {
    return pq[i] > pq[j]
}

func (pq PriorityQueue) Swap(i, j int) {
    pq[i], pq[j] = pq[j], pq[i]
}

func (pq *PriorityQueue) Push(x any) {
    *pq = append(*pq, x.(float64))
}

func (pq *PriorityQueue) Pop() any {
    old, n := *pq, len(*pq)
    x := old[n - 1]
    *pq = old[0 : n-1]
    return x
}

func halveArray(nums []int) int {
    pq := &PriorityQueue{}
    sum, sum2 := 0.0, 0.0
    for _, x := range nums {
        heap.Push(pq, float64(x))
        sum += float64(x)
    }
    res := 0
    for sum2 < sum / 2 {
        x := heap.Pop(pq).(float64)
        sum2 += x / 2
        heap.Push(pq, x / 2)
        res++
    }
    return res
}