CF1852A Ntarsis' Set

Ntarsis 得到一个集合 $S$，初始时包含整数 $1, 2, 3, \ldots, 10^{1000}$，并且是有序的。每天，他会同时移除 $S$ 中第 $a_1$ 小、第 $a_2$ 小、$\ldots$、第 $a_n$ 小的数。 $k$ 天后，$S$ 中最小的元素是多少？

每个测试点包含多组测试数据。第一行包含测试用例数 $t$（$1 \le t \le 10^5$）。接下来是每组测试数据的描述。 每组测试数据的第一行包含两个整数 $n$ 和 $k$（$1 \leq n, k \leq 2 \times 10^5$），分别表示数组 $a$ 的长度和天数。 接下来一行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \leq a_i \leq 10^9$），表示数组 $a$ 的元素。 保证： - 所有测试用例中 $n$ 的总和不超过 $2 \times 10^5$； - 所有测试用例中 $k$ 的总和不超过 $2 \times 10^5$； - 对于所有测试用例，$a_1 < a_2 < \cdots < a_n$。

对于每组测试数据，输出一个整数，表示 $k$ 天后 $S$ 中最小的元素。

对于第一个测试用例，每天需要移除 $S$ 中第 $1$ 小、第 $2$ 小、第 $4$ 小、第 $5$ 小和第 $6$ 小的元素。因此第一天后，$S$ 变为 $\require{cancel} \{\cancel 1, \cancel 2, 3, \cancel 4, \cancel 5, \cancel 6, 7, 8, 9, \ldots\} = \{3, 7, 8, 9, \ldots\}$。此时最小的元素是 $3$。 对于第二个测试用例，每天需要移除 $S$ 中第 $1$ 小、第 $3$ 小、第 $5$ 小、第 $6$ 小和第 $7$ 小的元素。$S$ 的变化如下： | 天数 | 移除前 $S$ | 移除后 $S$ | |---|---|---| | 1 | $\{\cancel 1, 2, \cancel 3, 4, \cancel 5, \cancel 6, \cancel 7, 8, 9, 10, \ldots\}$ | $\{2, 4, 8, 9, 10, \ldots\}$ | | 2 | $\{\cancel 2, 4, \cancel 8, 9, \cancel{10}, \cancel{11}, \cancel{12}, 13, 14, 15, \ldots\}$ | $\{4, 9, 13, 14, 15, \ldots\}$ | | 3 | $\{\cancel 4, 9, \cancel{13}, 14, \cancel{15}, \cancel{16}, \cancel{17}, 18, 19, 20, \ldots\}$ | $\{9, 14, 18, 19, 20, \ldots\}$ | $k=3$ 天后剩下的最小元素是 $9$。 由 ChatGPT 4.1 翻译