A16151 | Ntarsis' Set
时间限制1s
内存限制256MB
通过 / 提交0/0
题目描述
Ntarsis has been given a set $S$ , initially containing integers $1, 2, 3, \ldots, 10^{1000}$ in sorted order. Every day, he will remove the $a_1$ -th, $a_2$ -th, $\ldots$ , $a_n$ -th smallest numbers in $S$ simultaneously.
What is the smallest element in $S$ after $k$ days?
What is the smallest element in $S$ after $k$ days?
输入格式
Each test contains multiple test cases. The first line contains the number of test cases $t$ ( $1 \le t \le 10^5$ ). The description of the test cases follows.
The first line of each test case consists of two integers $n$ and $k$ ( $1 \leq n,k \leq 2 \cdot 10^5$ ) — the length of $a$ and the number of days.
The following line of each test case consists of $n$ integers $a_1, a_2, \ldots, a_n$ ( $1 \leq a_i \leq 10^9$ ) — the elements of array $a$ .
It is guaranteed that:
- The sum of $n$ over all test cases won't exceed $2 \cdot 10^5$ ;
- The sum of $k$ over all test cases won't exceed $2 \cdot 10^5$ ;
- $a_1 < a_2 < \cdots < a_n$ for all test cases.
The first line of each test case consists of two integers $n$ and $k$ ( $1 \leq n,k \leq 2 \cdot 10^5$ ) — the length of $a$ and the number of days.
The following line of each test case consists of $n$ integers $a_1, a_2, \ldots, a_n$ ( $1 \leq a_i \leq 10^9$ ) — the elements of array $a$ .
It is guaranteed that:
- The sum of $n$ over all test cases won't exceed $2 \cdot 10^5$ ;
- The sum of $k$ over all test cases won't exceed $2 \cdot 10^5$ ;
- $a_1 < a_2 < \cdots < a_n$ for all test cases.
输出格式
For each test case, print an integer that is the smallest element in $S$ after $k$ days.
输入输出样例
输入 #1
7 5 1 1 2 4 5 6 5 3 1 3 5 6 7 4 1000 2 3 4 5 9 1434 1 4 7 9 12 15 17 18 20 10 4 1 3 5 7 9 11 13 15 17 19 10 6 1 4 7 10 13 16 19 22 25 28 10 150000 1 3 4 5 10 11 12 13 14 15
输出 #1
3 9 1 12874 16 18 1499986
For the first test case, each day the $1$ -st, $2$ -nd, $4$ -th, $5$ -th, and $6$ -th smallest elements need to be removed from $S$ . So after the first day, $S$ will become $\require{cancel}$ $\{\cancel 1, \cancel 2, 3, \cancel 4, \cancel 5, \cancel 6, 7, 8, 9, \ldots\} = \{3, 7, 8, 9, \ldots\}$ . The smallest element is $3$ .
For the second case, each day the $1$ -st, $3$ -rd, $5$ -th, $6$ -th and $7$ -th smallest elements need to be removed from $S$ . $S$ will be changed as follows:
Day $S$ before $S$ after1 $\{\cancel 1, 2, \cancel 3, 4, \cancel 5, \cancel 6, \cancel 7, 8, 9, 10, \ldots \}$ $\to$ $\{2, 4, 8, 9, 10, \ldots\}$ 2 $\{\cancel 2, 4, \cancel 8, 9, \cancel{10}, \cancel{11}, \cancel{12}, 13, 14, 15, \ldots\}$ $\to$ $\{4, 9, 13, 14, 15, \ldots\}$ 3 $\{\cancel 4, 9, \cancel{13}, 14, \cancel{15}, \cancel{16}, \cancel{17}, 18, 19, 20, \ldots\}$ $\to$ $\{9, 14, 18, 19, 20, \ldots\}$ The smallest element left after $k = 3$ days is $9$ .
For the second case, each day the $1$ -st, $3$ -rd, $5$ -th, $6$ -th and $7$ -th smallest elements need to be removed from $S$ . $S$ will be changed as follows:
Day $S$ before $S$ after1 $\{\cancel 1, 2, \cancel 3, 4, \cancel 5, \cancel 6, \cancel 7, 8, 9, 10, \ldots \}$ $\to$ $\{2, 4, 8, 9, 10, \ldots\}$ 2 $\{\cancel 2, 4, \cancel 8, 9, \cancel{10}, \cancel{11}, \cancel{12}, 13, 14, 15, \ldots\}$ $\to$ $\{4, 9, 13, 14, 15, \ldots\}$ 3 $\{\cancel 4, 9, \cancel{13}, 14, \cancel{15}, \cancel{16}, \cancel{17}, 18, 19, 20, \ldots\}$ $\to$ $\{9, 14, 18, 19, 20, \ldots\}$ The smallest element left after $k = 3$ days is $9$ .
C++ 编辑器
输入
输出
可保存默认模板；新题优先使用已保存模板。
当前快捷键仅展示，暂不支持修改。
- 撤销
Ctrl / ⌘ + Z - 重做
Ctrl / ⌘ + Y - 查找
Ctrl / ⌘ + F - 全选
Ctrl / ⌘ + A - 复制
Ctrl / ⌘ + C - 剪切
Ctrl / ⌘ + X - 粘贴
Ctrl / ⌘ + V - 自动排版
工具栏排版按钮 - 草稿保存
编辑时自动保存到本机
历史
提交记录
状态说明时间源码
AI
作答助手
你好，我是作答助手。可以问思路、复杂度、样例含义或代码报错原因；不会直接给出完整 AC 代码。
确定要清空代码吗？
提交通过
评测结果：Accepted