309468: CF1684E. MEX vs DIFF
Memory Limit：256 MB
Time Limit：2 S
Judge Style：Text Compare
Creator：
Submit：0
Solved：0
Description
MEX vs DIFF
题意翻译
### 题目描述 给你一个大小为n的数组a，保证数组内元素非负，你可以执行以下操作k次： 在一次操作中将数组内任意一个数字改为任何一个非负整数。 现在定义这个数组的成本为DIFF(a)−MEX(a)，其中 DIFF(a) 为a数组内元素去重后的数量， MEX(a) 为数组中未出现的元素中最小的元素， 举个例子，MEX( { 1 , 2 , 3 } )=0 , MEX( { 0 , 1 , 2 , 4 , 5 } ) = 3。 现在给你数组a，求能实现的最小成本。 ### 输入格式 输入包含多个测试用例，第一行输入t表示数据组数，测试用例描述如下： 每个用例的第一行包含两个整数n和k，n表示数组长度，k表示最多的操作次数，第二行有n个整数，为数组n的元素。 ### 输出格式 对于每个测试用例输出一行一个整数，表示该用例能实现的最小整数。 ### 样例说明/提示 在第一个测试用例中，不需要任何操作来最小化 DIFF-MEX 的值。 在第二个测试用例中，可以将 5 替换为 1 。 数组 a 变为[ 0 , 2 , 4 , 1 ] , DIFF = 4，MEX=MEX( { 0 , 1 , 2 , 4 } )=3 ，所以答案是 1. 在第三个测试用例中，一个可能的数组 a 的变形是[ 4 , 13 , 0 , 0 , 13 , 1 , 2 ]，其中 DIFF = 5，MEX = 3。 在第四个测试用例中，一个可能的数组 a 的变形是 [ 1 , 2 , 3 , 0 , 0 , 0 ] 。题目描述
You are given an array $ a $ of $ n $ non-negative integers. In one operation you can change any number in the array to any other non-negative integer. Let's define the cost of the array as $ \operatorname{DIFF}(a) - \operatorname{MEX}(a) $ , where $ \operatorname{MEX} $ of a set of non-negative integers is the smallest non-negative integer not present in the set, and $ \operatorname{DIFF} $ is the number of different numbers in the array. For example, $ \operatorname{MEX}(\{1, 2, 3\}) = 0 $ , $ \operatorname{MEX}(\{0, 1, 2, 4, 5\}) = 3 $ . You should find the minimal cost of the array $ a $ if you are allowed to make at most $ k $ operations.输入输出格式
输入格式
The input consists of multiple test cases. The first line contains a single integer $ t $ ( $ 1 \le t \le 10^4 $ ) — the number of test cases. Description of the test cases follows. The first line of each test case contains two integers $ n $ and $ k $ ( $ 1 \le n \le 10^5 $ , $ 0 \le k \le 10^5 $ ) — the length of the array $ a $ and the number of operations that you are allowed to make. The second line of each test case contains $ n $ integers $ a_1, a_2, \ldots, a_n $ ( $ 0 \le a_i \le 10^9 $ ) — the elements of the array $ a $ . It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 10^5 $ .
输出格式
For each test case output a single integer — minimal cost that it is possible to get making at most $ k $ operations.
输入输出样例
输入样例 #1
4
4 1
3 0 1 2
4 1
0 2 4 5
7 2
4 13 0 0 13 1337 1000000000
6 2
1 2 8 0 0 0输出样例 #1
0
1
2
0说明
In the first test case no operations are needed to minimize the value of $ \operatorname{DIFF} - \operatorname{MEX} $ . In the second test case it is possible to replace $ 5 $ by $ 1 $ . After that the array $ a $ is $ [0,\, 2,\, 4,\, 1] $ , $ \operatorname{DIFF} = 4 $ , $ \operatorname{MEX} = \operatorname{MEX}(\{0, 1, 2, 4\}) = 3 $ , so the answer is $ 1 $ . In the third test case one possible array $ a $ is $ [4,\, 13,\, 0,\, 0,\, 13,\, 1,\, 2] $ , $ \operatorname{DIFF} = 5 $ , $ \operatorname{MEX} = 3 $ . In the fourth test case one possible array $ a $ is $ [1,\, 2,\, 3,\, 0,\, 0,\, 0] $ .Input
题意翻译
### 题目描述 给你一个大小为n的数组a，保证数组内元素非负，你可以执行以下操作k次： 在一次操作中将数组内任意一个数字改为任何一个非负整数。 现在定义这个数组的成本为DIFF(a)−MEX(a)，其中 DIFF(a) 为a数组内元素去重后的数量， MEX(a) 为数组中未出现的元素中最小的元素， 举个例子，MEX( { 1 , 2 , 3 } )=0 , MEX( { 0 , 1 , 2 , 4 , 5 } ) = 3。 现在给你数组a，求能实现的最小成本。 ### 输入格式 输入包含多个测试用例，第一行输入t表示数据组数，测试用例描述如下： 每个用例的第一行包含两个整数n和k，n表示数组长度，k表示最多的操作次数，第二行有n个整数，为数组n的元素。 ### 输出格式 对于每个测试用例输出一行一个整数，表示该用例能实现的最小整数。 ### 样例说明/提示 在第一个测试用例中，不需要任何操作来最小化 DIFF-MEX 的值。 在第二个测试用例中，可以将 5 替换为 1 。 数组 a 变为[ 0 , 2 , 4 , 1 ] , DIFF = 4，MEX=MEX( { 0 , 1 , 2 , 4 } )=3 ，所以答案是 1. 在第三个测试用例中，一个可能的数组 a 的变形是[ 4 , 13 , 0 , 0 , 13 , 1 , 2 ]，其中 DIFF = 5，MEX = 3。 在第四个测试用例中，一个可能的数组 a 的变形是 [ 1 , 2 , 3 , 0 , 0 , 0 ] 。Output
**题意翻译**
题目描述：给定一个含有n个非负整数的数组a，可以进行以下操作k次：在每次操作中，可以将数组中的任意一个数字改为任意一个非负整数。定义数组a的成本为DIFF(a)−MEX(a)，其中DIFF(a)是数组a去重后的元素数量，MEX(a)是数组中未出现的最小非负整数。例如，MEX({1, 2, 3})=0, MEX({0, 1, 2, 4, 5})=3。给定数组a，求进行最多k次操作后能实现的最小成本。
输入格式：输入包含多个测试用例，第一行输入t表示数据组数，测试用例描述如下：
每个用例的第一行包含两个整数n和k，n表示数组长度，k表示最多的操作次数，第二行有n个整数，为数组n的元素。
输出格式：对于每个测试用例输出一行一个整数，表示该用例能实现的最小整数。
样例说明/提示：在第一个测试用例中，不需要任何操作来最小化DIFF-MEX的值。在第二个测试用例中，可以将5替换为1。数组a变为[0, 2, 4, 1], DIFF=4，MEX=MEX({0, 1, 2, 4})=3，所以答案是1。在第三个测试用例中，一个可能的数组a的变形是[4, 13, 0, 0, 13, 1, 2]，其中DIFF=5，MEX=3。在第四个测试用例中，一个可能的数组a的变形是[1, 2, 3, 0, 0, 0]。
**题目描述**
You are given an array $ a $ of $ n $ non-negative integers. In one operation you can change any number in the array to any other non-negative integer.
Let's define the cost of the array as $ \operatorname{DIFF}(a) - \operatorname{MEX}(a) $, where $ \operatorname{MEX} $ of a set of non-negative integers is the smallest non-negative integer not present in the set, and $ \operatorname{DIFF} $ is the number of different numbers in the array.
For example, $ \operatorname{MEX}(\{1, 2, 3\}) = 0 $, $ \operatorname{MEX}(\{0, 1, 2, 4, 5\}) = 3 $.
You should find the minimal cost of the array $ a $ if you are allowed to make at most $ k $ operations.
**输入输出格式**
输入格式：输入由多个测试用例组成。第一行包含一个整数 $ t $ ($ 1 \le t \le 10^4 $) — 测试用例的数量。接下来是每个测试用例的描述。
每个测试用例的第一行包含两个整数 $ n $ 和 $ k $ ($ 1 \le n \le 10^5 $, $ 0 \le k \le 10^5 $) — 数组 $ a $ 的长度和允许进行的操作次数。
每个测试用例的第二行包含 $ n $ 个整数 $ a_1, a_2, \ldots, a_n $ ($ 0 \le a_i \le 10^9 $) — 数组 $ a $ 的元素。
保证所有测试用例的 $ n $ 之和不超过 $ 10^5 $。
输出格式：对于每个测试用例输出一个整数 — 在进行最多 $ k $ 次操作后可能获得的最小成本。
**输入输出样例**
输入样例 #1：
```
4
4 1
3 0 1 2
4 1
0 2 4 5
7 2
4 13 0 0 13 1337 1000000000
6 2
1 2 8 0 0 0
```
输出样例 #1：
```
0
1
2
0
```
说明：在第一个测试用例中，不需要任何操作来最小化 $ \operatorname{DIFF} - \operatorname{MEX} $ 的值。在第二个测试用例中，可以将 5 替换为 1 。数组 $ a $ 变为 [0, 2, 4, 1], $ \operatorname{DIFF} = 4 $, $ \operatorname{MEX} = \operatorname{MEX}(\{0, 1, 2, 4\}) = 3 $, 所以答案是 1。在第三个测试用例中，一个可能的数组 $ a $**题意翻译** 题目描述：给定一个含有n个非负整数的数组a，可以进行以下操作k次：在每次操作中，可以将数组中的任意一个数字改为任意一个非负整数。定义数组a的成本为DIFF(a)−MEX(a)，其中DIFF(a)是数组a去重后的元素数量，MEX(a)是数组中未出现的最小非负整数。例如，MEX({1, 2, 3})=0, MEX({0, 1, 2, 4, 5})=3。给定数组a，求进行最多k次操作后能实现的最小成本。 输入格式：输入包含多个测试用例，第一行输入t表示数据组数，测试用例描述如下： 每个用例的第一行包含两个整数n和k，n表示数组长度，k表示最多的操作次数，第二行有n个整数，为数组n的元素。 输出格式：对于每个测试用例输出一行一个整数，表示该用例能实现的最小整数。 样例说明/提示：在第一个测试用例中，不需要任何操作来最小化DIFF-MEX的值。在第二个测试用例中，可以将5替换为1。数组a变为[0, 2, 4, 1], DIFF=4，MEX=MEX({0, 1, 2, 4})=3，所以答案是1。在第三个测试用例中，一个可能的数组a的变形是[4, 13, 0, 0, 13, 1, 2]，其中DIFF=5，MEX=3。在第四个测试用例中，一个可能的数组a的变形是[1, 2, 3, 0, 0, 0]。 **题目描述** You are given an array $ a $ of $ n $ non-negative integers. In one operation you can change any number in the array to any other non-negative integer. Let's define the cost of the array as $ \operatorname{DIFF}(a) - \operatorname{MEX}(a) $, where $ \operatorname{MEX} $ of a set of non-negative integers is the smallest non-negative integer not present in the set, and $ \operatorname{DIFF} $ is the number of different numbers in the array. For example, $ \operatorname{MEX}(\{1, 2, 3\}) = 0 $, $ \operatorname{MEX}(\{0, 1, 2, 4, 5\}) = 3 $. You should find the minimal cost of the array $ a $ if you are allowed to make at most $ k $ operations. **输入输出格式** 输入格式：输入由多个测试用例组成。第一行包含一个整数 $ t $ ($ 1 \le t \le 10^4 $) — 测试用例的数量。接下来是每个测试用例的描述。 每个测试用例的第一行包含两个整数 $ n $ 和 $ k $ ($ 1 \le n \le 10^5 $, $ 0 \le k \le 10^5 $) — 数组 $ a $ 的长度和允许进行的操作次数。 每个测试用例的第二行包含 $ n $ 个整数 $ a_1, a_2, \ldots, a_n $ ($ 0 \le a_i \le 10^9 $) — 数组 $ a $ 的元素。 保证所有测试用例的 $ n $ 之和不超过 $ 10^5 $。 输出格式：对于每个测试用例输出一个整数 — 在进行最多 $ k $ 次操作后可能获得的最小成本。 **输入输出样例** 输入样例 #1： ``` 4 4 1 3 0 1 2 4 1 0 2 4 5 7 2 4 13 0 0 13 1337 1000000000 6 2 1 2 8 0 0 0 ``` 输出样例 #1： ``` 0 1 2 0 ``` 说明：在第一个测试用例中，不需要任何操作来最小化 $ \operatorname{DIFF} - \operatorname{MEX} $ 的值。在第二个测试用例中，可以将 5 替换为 1 。数组 $ a $ 变为 [0, 2, 4, 1], $ \operatorname{DIFF} = 4 $, $ \operatorname{MEX} = \operatorname{MEX}(\{0, 1, 2, 4\}) = 3 $, 所以答案是 1。在第三个测试用例中，一个可能的数组 $ a $
题目描述：给定一个含有n个非负整数的数组a，可以进行以下操作k次：在每次操作中，可以将数组中的任意一个数字改为任意一个非负整数。定义数组a的成本为DIFF(a)−MEX(a)，其中DIFF(a)是数组a去重后的元素数量，MEX(a)是数组中未出现的最小非负整数。例如，MEX({1, 2, 3})=0, MEX({0, 1, 2, 4, 5})=3。给定数组a，求进行最多k次操作后能实现的最小成本。
输入格式：输入包含多个测试用例，第一行输入t表示数据组数，测试用例描述如下：
每个用例的第一行包含两个整数n和k，n表示数组长度，k表示最多的操作次数，第二行有n个整数，为数组n的元素。
输出格式：对于每个测试用例输出一行一个整数，表示该用例能实现的最小整数。
样例说明/提示：在第一个测试用例中，不需要任何操作来最小化DIFF-MEX的值。在第二个测试用例中，可以将5替换为1。数组a变为[0, 2, 4, 1], DIFF=4，MEX=MEX({0, 1, 2, 4})=3，所以答案是1。在第三个测试用例中，一个可能的数组a的变形是[4, 13, 0, 0, 13, 1, 2]，其中DIFF=5，MEX=3。在第四个测试用例中，一个可能的数组a的变形是[1, 2, 3, 0, 0, 0]。
**题目描述**
You are given an array $ a $ of $ n $ non-negative integers. In one operation you can change any number in the array to any other non-negative integer.
Let's define the cost of the array as $ \operatorname{DIFF}(a) - \operatorname{MEX}(a) $, where $ \operatorname{MEX} $ of a set of non-negative integers is the smallest non-negative integer not present in the set, and $ \operatorname{DIFF} $ is the number of different numbers in the array.
For example, $ \operatorname{MEX}(\{1, 2, 3\}) = 0 $, $ \operatorname{MEX}(\{0, 1, 2, 4, 5\}) = 3 $.
You should find the minimal cost of the array $ a $ if you are allowed to make at most $ k $ operations.
**输入输出格式**
输入格式：输入由多个测试用例组成。第一行包含一个整数 $ t $ ($ 1 \le t \le 10^4 $) — 测试用例的数量。接下来是每个测试用例的描述。
每个测试用例的第一行包含两个整数 $ n $ 和 $ k $ ($ 1 \le n \le 10^5 $, $ 0 \le k \le 10^5 $) — 数组 $ a $ 的长度和允许进行的操作次数。
每个测试用例的第二行包含 $ n $ 个整数 $ a_1, a_2, \ldots, a_n $ ($ 0 \le a_i \le 10^9 $) — 数组 $ a $ 的元素。
保证所有测试用例的 $ n $ 之和不超过 $ 10^5 $。
输出格式：对于每个测试用例输出一个整数 — 在进行最多 $ k $ 次操作后可能获得的最小成本。
**输入输出样例**
输入样例 #1：
```
4
4 1
3 0 1 2
4 1
0 2 4 5
7 2
4 13 0 0 13 1337 1000000000
6 2
1 2 8 0 0 0
```
输出样例 #1：
```
0
1
2
0
```
说明：在第一个测试用例中，不需要任何操作来最小化 $ \operatorname{DIFF} - \operatorname{MEX} $ 的值。在第二个测试用例中，可以将 5 替换为 1 。数组 $ a $ 变为 [0, 2, 4, 1], $ \operatorname{DIFF} = 4 $, $ \operatorname{MEX} = \operatorname{MEX}(\{0, 1, 2, 4\}) = 3 $, 所以答案是 1。在第三个测试用例中，一个可能的数组 $ a $**题意翻译** 题目描述：给定一个含有n个非负整数的数组a，可以进行以下操作k次：在每次操作中，可以将数组中的任意一个数字改为任意一个非负整数。定义数组a的成本为DIFF(a)−MEX(a)，其中DIFF(a)是数组a去重后的元素数量，MEX(a)是数组中未出现的最小非负整数。例如，MEX({1, 2, 3})=0, MEX({0, 1, 2, 4, 5})=3。给定数组a，求进行最多k次操作后能实现的最小成本。 输入格式：输入包含多个测试用例，第一行输入t表示数据组数，测试用例描述如下： 每个用例的第一行包含两个整数n和k，n表示数组长度，k表示最多的操作次数，第二行有n个整数，为数组n的元素。 输出格式：对于每个测试用例输出一行一个整数，表示该用例能实现的最小整数。 样例说明/提示：在第一个测试用例中，不需要任何操作来最小化DIFF-MEX的值。在第二个测试用例中，可以将5替换为1。数组a变为[0, 2, 4, 1], DIFF=4，MEX=MEX({0, 1, 2, 4})=3，所以答案是1。在第三个测试用例中，一个可能的数组a的变形是[4, 13, 0, 0, 13, 1, 2]，其中DIFF=5，MEX=3。在第四个测试用例中，一个可能的数组a的变形是[1, 2, 3, 0, 0, 0]。 **题目描述** You are given an array $ a $ of $ n $ non-negative integers. In one operation you can change any number in the array to any other non-negative integer. Let's define the cost of the array as $ \operatorname{DIFF}(a) - \operatorname{MEX}(a) $, where $ \operatorname{MEX} $ of a set of non-negative integers is the smallest non-negative integer not present in the set, and $ \operatorname{DIFF} $ is the number of different numbers in the array. For example, $ \operatorname{MEX}(\{1, 2, 3\}) = 0 $, $ \operatorname{MEX}(\{0, 1, 2, 4, 5\}) = 3 $. You should find the minimal cost of the array $ a $ if you are allowed to make at most $ k $ operations. **输入输出格式** 输入格式：输入由多个测试用例组成。第一行包含一个整数 $ t $ ($ 1 \le t \le 10^4 $) — 测试用例的数量。接下来是每个测试用例的描述。 每个测试用例的第一行包含两个整数 $ n $ 和 $ k $ ($ 1 \le n \le 10^5 $, $ 0 \le k \le 10^5 $) — 数组 $ a $ 的长度和允许进行的操作次数。 每个测试用例的第二行包含 $ n $ 个整数 $ a_1, a_2, \ldots, a_n $ ($ 0 \le a_i \le 10^9 $) — 数组 $ a $ 的元素。 保证所有测试用例的 $ n $ 之和不超过 $ 10^5 $。 输出格式：对于每个测试用例输出一个整数 — 在进行最多 $ k $ 次操作后可能获得的最小成本。 **输入输出样例** 输入样例 #1： ``` 4 4 1 3 0 1 2 4 1 0 2 4 5 7 2 4 13 0 0 13 1337 1000000000 6 2 1 2 8 0 0 0 ``` 输出样例 #1： ``` 0 1 2 0 ``` 说明：在第一个测试用例中，不需要任何操作来最小化 $ \operatorname{DIFF} - \operatorname{MEX} $ 的值。在第二个测试用例中，可以将 5 替换为 1 。数组 $ a $ 变为 [0, 2, 4, 1], $ \operatorname{DIFF} = 4 $, $ \operatorname{MEX} = \operatorname{MEX}(\{0, 1, 2, 4\}) = 3 $, 所以答案是 1。在第三个测试用例中，一个可能的数组 $ a $