#CF2021B. 最大化 MEX
最大化 MEX
B. 最大化 MEX
每次测试时间限制: 秒
内存限制: 兆字节
给定一个由 个正整数组成的数组 和一个整数 。
你可以执行以下两步操作任意次(包括零次):
- 选择一个下标 ()。
- 将 增加 ,即 。
如果以最优方式执行操作,求数组 的 MEX 的最大可能值。
MEX(最小排除值) 是指不在数组中的最小非负整数。例如:
- 的 MEX 是 ,因为 不在数组中。
- 的 MEX 是 ,因为 和 都在数组中,但 不在。
- 的 MEX 是 ,因为 都在数组中,但 不在。
输入格式
每个测试包含多个测试用例。第一行包含测试用例数 ()。
每个测试用例的第一行包含两个整数 和 (,)——数组长度和操作中的整数 。
每个测试用例的第二行包含 个整数 ()——给定的数组。
保证所有测试用例的 之和不超过 。
输出格式
对于每个测试用例,输出一个整数:以最优方式执行操作后,数组 的最大可能 MEX。
示例
输入:
3
6 3
0 3 2 1 5 2
6 2
1 3 4 1 0 2
4 5
2 5 10 3
输出:
4
6
0
说明
- 第一个测试用例:不进行任何操作时,MEX 已经是 ,这是最大值。
- 第二个测试用例:不进行操作时 MEX 为 。如果对 执行两次操作,数组变为 ,此时 MEX 变为 ,这是最大值。
- 第三个测试用例:不进行操作时 MEX 已经是 ,这是最大值。