[Python problem solution] 100232. Minimum number of operations exceeding the threshold II

Topic: 100232. Minimum number of operations exceeding threshold II

Question description

Minimum number of operations exceeding threshold II

Given an array of integers starting from 0 nums and an integer k. You can do the following:

• Choose nums The smallest two integers in x and y。
• will x and y from nums Delete in.
• will min(x, y) * 2 + max(x, y) Add to any position in the array.

Note that only if nums You can only perform the above operations if it contains at least two elements.

The goal is to make all elements in the array greater than or equal to k. Please return the minimum number of operations required to achieve this goal.

Example

1. Example 1:

   • Input:nums = [2,11,10,1,3], k = 10
   • Output:2
   • Explanation: In the first operation, we remove elements 1 and 2 and then add 1_2 + 2 to nums in,nums become [4, 11, 10, 3]. In the second operation, we remove elements 3 and 4 and add 3_2 + 4 to nums in,nums become [10, 11, 10]. At this point, all elements in the array are greater than or equal to 10, so we stop. The minimum number of operations required is 2.

2. Example 2:

   • Input:nums = [1,1,2,4,9], k = 20
   • Output:4
   • Explanation: After the first operation,nums become [2, 4, 9, 3]. After the second operation,nums become [7, 4, 9]. After the third operation,nums become [15, 9]. After the fourth operation,nums become [33]. At this point, all elements in the array are greater than or equal to 20, so we stop. The minimum number of operations required is 4.

Tips

• 2 <= nums.length <= 2 * 10^5
• 1 <= nums[i] <= 10^9
• 1 <= k <= 10^9
• The input guarantees that the answer must exist, that is to say, there must be a sequence of operations that makes all elements in the array greater than or equal to k。

solution strategy

This problem can be solved efficiently by greedy algorithm and min-heap. We select the smallest two numbers from the array for operation each time, so that the sum of the numbers can be increased fastest and the threshold can be reached or exceeded faster. k. The steps are as follows:

1. initialization: Convert an array into a min-heap to quickly find the smallest two numbers.

2. perform operations: Repeat the following steps until all elements in the array are greater than or equal to k：

   • Pop the smallest two elements from the heap x and y。
   • will 2 * min(x, y) + max(x, y) Added back to the pile.
   • Record the number of operations.

3. Return results: when all elements are greater than or equal to k When , return the number of operations.

Code implementation

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

import heapq

def min_operations_to_reach_k(nums, k):
    # 将数组转换成最小堆
    heapq.heapify(nums)
    operations = 0

    # 当最小的元素小于k时，继续操作
    while nums[0] < k:
        # 如果数组中只剩一个元素，则无法进行操作
        if len(nums) < 2:
            return -1  # 返回-1表示无法达到目标

        # 弹出最小的两个元素
        x = heapq.heappop(nums)
        y = heapq.heappop(nums)

        # 将新元素插入堆中
        heapq.heappush(nums, 2 * min(x, y) + max(x, y))

        # 增加操作计数
        operations += 1

    return operations

# 测试代码
print(min_operations_to_reach_k([2, 11, 10, 1, 3], 10))  # 应为2
print(min_operations_to_reach_k([1, 1, 2, 4, 9], 20))  # 应为4

This code uses Python's heapq Module to effectively manage the minimum heap to ensure that the smallest two numbers can be found quickly every time. In this way, we can solve this problem efficiently.