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] $ .