Question

3066. 超过阈值的最少操作数 II

English Version

题目描述

给你一个下标从 0 开始的整数数组 nums 和一个整数 k 。

一次操作中，你将执行：

• 选择 nums 中最小的两个整数 x 和 y 。
• 将 x 和 y 从 nums 中删除。
• 将 min(x, y) * 2 + max(x, y) 添加到数组中的任意位置。

注意，只有当 nums 至少包含两个元素时，你才可以执行以上操作。

你需要使数组中的所有元素都大于或等于 k ，请你返回需要的 最少 操作次数。

 

示例 1：

输入：nums = [2,11,10,1,3], k = 10
输出：2
解释：第一次操作中，我们删除元素 1 和 2 ，然后添加 1 * 2 + 2 到 nums 中，nums 变为 [4, 11, 10, 3] 。
第二次操作中，我们删除元素 3 和 4 ，然后添加 3 * 2 + 4 到 nums 中，nums 变为 [10, 11, 10] 。
此时，数组中的所有元素都大于等于 10 ，所以我们停止操作。
使数组中所有元素都大于等于 10 需要的最少操作次数为 2 。

示例 2：

输入：nums = [1,1,2,4,9], k = 20
输出：4
解释：第一次操作后，nums 变为 [2, 4, 9, 3] 。
第二次操作后，nums 变为 [7, 4, 9] 。
第三次操作后，nums 变为 [15, 9] 。
第四次操作后，nums 变为 [33] 。
此时，数组中的所有元素都大于等于 20 ，所以我们停止操作。
使数组中所有元素都大于等于 20 需要的最少操作次数为 4 。

 

提示：

• 2 <= nums.length <= 2 * 105
• 1 <= nums[i] <= 109
• 1 <= k <= 109
• 输入保证答案一定存在，也就是说一定存在一个操作序列使数组中所有元素都大于等于 k 。

解法

方法一：优先队列（小根堆）

我们可以使用优先队列（小根堆）来模拟这个过程。

具体地，我们先将数组中的元素加入优先队列 $pq$ 中。然后我们不断地从优先队列中取出两个最小的元素 $x$ 和 $y$，将 $\min(x, y) \times 2 + \max(x, y)$ 放回优先队列中。每次操作后，我们将操作次数加一。当队列中的元素个数小于 $2$ 或者队列中的最小元素大于等于 $k$ 时，我们停止操作。

时间复杂度 $O(n \times \log n)$，空间复杂度 $O(n)$。其中 $n$ 为数组长度。

class Solution:
  def minOperations(self, nums: List[int], k: int) -> int:
    heapify(nums)
    ans = 0
    while len(nums) > 1 and nums[0] < k:
      x, y = heappop(nums), heappop(nums)
      heappush(nums, min(x, y) * 2 + max(x, y))
      ans += 1
    return ans

class Solution {
  public int minOperations(int[] nums, int k) {
    PriorityQueue<Long> pq = new PriorityQueue<>();
    for (int x : nums) {
      pq.offer((long) x);
    }
    int ans = 0;
    for (; pq.size() > 1 && pq.peek() < k; ++ans) {
      long x = pq.poll(), y = pq.poll();
      pq.offer(Math.min(x, y) * 2 + Math.max(x, y));
    }
    return ans;
  }
}

class Solution {
public:
  int minOperations(vector<int>& nums, int k) {
    using ll = long long;
    priority_queue<ll, vector<ll>, greater<ll>> pq;
    for (int x : nums) {
      pq.push(x);
    }
    int ans = 0;
    for (; pq.size() > 1 && pq.top() < k; ++ans) {
      ll x = pq.top();
      pq.pop();
      ll y = pq.top();
      pq.pop();
      pq.push(min(x, y) * 2 + max(x, y));
    }
    return ans;
  }
};

func minOperations(nums []int, k int) (ans int) {
  pq := &hp{nums}
  heap.Init(pq)
  for ; pq.Len() > 1 && pq.IntSlice[0] < k; ans++ {
    x, y := heap.Pop(pq).(int), heap.Pop(pq).(int)
    heap.Push(pq, min(x, y)*2+max(x, y))
  }
  return
}

type hp struct{ sort.IntSlice }

func (h *hp) Less(i, j int) bool { return h.IntSlice[i] < h.IntSlice[j] }
func (h *hp) Pop() interface{} {
  old := h.IntSlice
  n := len(old)
  x := old[n-1]
  h.IntSlice = old[0 : n-1]
  return x
}
func (h *hp) Push(x interface{}) {
  h.IntSlice = append(h.IntSlice, x.(int))
}

function minOperations(nums: number[], k: number): number {
  const pq = new MinPriorityQueue();
  for (const x of nums) {
    pq.enqueue(x);
  }
  let ans = 0;
  for (; pq.size() > 1 && pq.front().element < k; ++ans) {
    const x = pq.dequeue().element;
    const y = pq.dequeue().element;
    pq.enqueue(Math.min(x, y) * 2 + Math.max(x, y));
  }
  return ans;
}