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 $

加入题单

算法标签: