摘要: 过程模拟导论

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

在现实世界中，有许多问题我们可以通过模拟它们的过程来解决。这类问题被称为模拟问题。对于这些问题，解决方案的步骤和规则会在问题描述中展示。程序必须根据描述来模拟过程或实现规则。通常有两种类型的模拟：随机模拟和过程模拟。

随机模拟的问题，其步骤和规则中有概率的因素，程序利用随机函数和取整函数得到一个符合要求的随机值。然后设计算法实现步骤和规则，观察在不同输入下的结果。随机模拟可以解决很多实际问题，但由于其不确定性，对同一输入可能会有不同的输出，在需要上机提交代码的编程题目当中很少出现随机模拟的问题。

过程模拟的问题，其步骤和规则都是确定性的，直接针对步骤和规则来设计算法，观察不同输入下的结果即可。此时算法的输出完全依赖于过程模拟的真实性与正确性，没有任何不确定性。因此有不少算法题是过程模拟的问题。在工作中会遇到一些需要复现结果的场合，基本上也可以算是过程模拟，它的步骤和规则可能来自论文、也可能来自业务逻辑，因此过程模拟是一个比较实用的思想。

过程模拟有三种比较常见的类型：

• 通过直接陈述进行的模拟；
• 通过筛法进行的模拟；
• 通过构造进行的模拟。

后续我们会通过一些例题分别看一下这些模拟的类型与场景。

本文我们看一个直接陈述的模拟题，从算法角度来看，关键点在于分析清楚步骤和规则中涉及到哪些操作，如何设计算法和数据结构高效地实现这些操作。

此前我们整理过一份模拟问题的题目清单，可以参考 leetcode模拟问题汇总。

题目

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

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

一次操作中，你将执行：

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

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

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

提示：

1
2
3
4

2 <= nums.length <= 2e5
1 <= nums[i] <= 1e9
1 <= k <= 1e9
输入保证答案一定存在，也就是说一定存在一个操作序列使数组中所有元素都大于等于 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 。

题解

算法: 过程模拟、堆

操作执行过程在题目描述中明确给出了，每次操作取最小的两个元素从集合中删除，然后新加进去一个元素，直至集合中所有元素都不小于 k。返回操作的步数。

给定输入的集合 nums，如果不把以上流程走一遍，很难知道操作次数是多少，因此我们需要模拟上述过程，只需要实现给定的步骤和规则即可，因此这是一个直接陈述的模拟。

可以看到对步骤和规则的模拟过程中，需要频繁地做以下操作：

• 找到集合中的最小元素
• 删除最小元素
• 插入新元素

这是一个典型的通过堆来维护的操作集合。于是可以给出以下算法：

1
2
3
4
5
6

用 nums 建立最小堆
ans = 0
只要堆中元素数不小于 2，且堆顶元素小于 k，就进行一轮操作：
    弹出最小的两个元素 x, y
    压入新元素 min(x, y) * 2 + max(x, y)
    ans += 1

代码 (Python)

1
2
3
4
5
6
7
8
9
10
11
12
13

import heapq

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

代码 (C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

#include <queue>

using namespace std;
using ll = long long;

class Solution {
public:
    int minOperations(vector<int>& nums, int k) {
        priority_queue<ll, vector<ll>, greater<ll>> pq(nums.begin(), nums.end());
        int ans = 0;
        while(pq.size() >= 2 && pq.top() < k)
        {
            ans++;
            ll x = pq.top();
            pq.pop();
            ll y = pq.top();
            pq.pop();
            pq.push(x + x + y);
        }
        return ans;
    }
};