← 返回题目列表

Codeforces · 2149/C

C. 墨西哥上涨

中文机器翻译题面 查看原题

给定一个长度为 $$$n$$$ 的数组 $$$a$$$ 和一个数字 $$$k$$$,其中 $$$0 \le k \le n$$$。

在一次操作中,您可以选择任何索引 $$$i$$$ ($$$1 \le i \le n$$$) 并将 $$$a_i$$$ 设置为 $$$[0,n]$$$ 范围内的任何整数值 $$$x$$$。

求满足条件所需的最少此类操作数:$$$\operatorname{MEX}(a)$$$$$$^{\text{*}}$$$$$$=k$$$

$$$^{\text{*}}$$$一组数字 $$$a_1,a_2,\dots,a_n$$$ 的最小排除值 (MEX) 是未出现在 $$$a_i$$$ 中的最小非负整数 $$$x$$$。

输入

每个测试都包含多组输入数据。

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 输入数据的组数。输入数据组的描述如下。

每组输入数据的第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \le n \le 2 \cdot 10^5,\,\, 0 \le k \le n$$$) — 数组 $$$a$$$ 的长度和所需的 $$$\operatorname{MEX}(a)$$$。

第二行包含 $$$n$$$ 整数 $$$a_1,a_2,\dots,a_n$$$ ($$$0 \le a_i \le n$$$) — 数组 $$$a$$$ 的元素。

保证所有输入数据集的 $$$n$$$ 值的总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每组输入数据,输出一个整数——满足条件 $$$\operatorname{MEX}(a)=k$$$ 所需的最少操作数。

示例

输入
复制

5
1 0
0
3 1
0 2 3
5 5
0 1 2 3 4
6 2
0 3 4 2 6 2
7 4
0 1 5 4 4 7 3

输出
复制

1
0
0
2
2

注意

在第一组输入数据中,数组$$$a=[0]$$$,因此$$$\operatorname{MEX}=1$$$。 $$$\\$$$ 通过删除零(用任何 $$$x\in[1,n]$$$ 替换它),我们得到 $$$\operatorname{MEX}=0$$$。 $$$\\$$$ 因此,只需要一项操作。

在第三组输入数据中,数组包含所有数字$$$0,1,2,3,4$$$,因此从一开始$$$\operatorname{MEX}(a)=5$$$。

由于这与所需的 $$$k$$$ 匹配,因此不需要进行任何更改,并且最小操作数为 $$$0$$$。