Ntarsis被赋予了一个集合 S 最初包含排序 123…10^1000 顺序的整数 。每天他都会同时删除 -th、 a1 -th、 … an 、 a2 -th 最小的数字 k天后 最小的 S 元素是什么？k最大为2e5ai最大为1e9

首先，我们可以观察到每一轮删除操作都是删除 S 中的一些数字。设 S 中最小的数字为 m，则在第 k 天，S 中的数字会减少 k 个，即 S 中的数字会减少 k 个最小的数字。因此，我们只需要找到第 k 天删除的数字的规律，就可以确定第 k 天最小的 S 元素。

观察删除的数字的规律：

• 第 1 天删除的数字是 a1-th 最小的数字，即 S 中的第 a1 个最小的数字。
• 第 2 天删除的数字是 a1-th、a2-th 最小的数字，即 S 中的第 a1+a2 个最小的数字。
• 第 3 天删除的数字是 a1-th、a2-th、a3-th 最小的数字，即 S 中的第 a1+a2+a3 个最小的数字。
• ...
• 第 k 天删除的数字是 a1-th、a2-th、...、ak-th 最小的数字，即 S 中的第 a1+a2+...+ak 个最小的数字。

由上述规律可知，第 k 天删除的数字是 S 中的第 a1+a2+...+ak 个最小的数字。

因此，我们可以使用一个变量 sum 来记录 a1+a2+...+ak 的值，初始化为 0。然后，对于每一天的删除操作，将 sum 更新为 sum+a[i]，其中 a[i] 是第 i 天删除的数字。最后，第 k 天最小的 S 元素就是 S 中的第 sum 个最小的数字。

需要注意的是，S 中的数字是从 1 开始排序的，而 a[i] 是指删除第 i 天的数字是 S 中的第 a[i] 个最小的数字。因此，我们需要将 a[i] 减去 1，使得 a[i] 变为从 0 开始计数的索引值。

伪代码如下：

sum = 0 for i = 1 to k: sum = sum + a[i] - 1

最小的 S 元素为 S[sum]。

此算法的时间复杂度为 O(k)，其中 k 最大为 2e5，因此算法是有效的