Codeforces Round 792 (Div. 1 + Div. 2) |
---|
Закончено |
У Тёти Люсине, как и у всех гениальных людей, имеются свои странности. Сегодня в качестве развлечения она решила посмотреть на противостояние двух могущественных функций. В зависимости от результата она решит, добавлять ли эти функции в CrowdScript.
Дан массив $$$a$$$ из $$$n$$$ неотрицательных целых чисел. За одну операцию вы можете заменить любое число в массиве на любое неотрицательное целое число.
Назовём стоимостью массива $$$\operatorname{DIFF}(a) - \operatorname{MEX}(a)$$$, где $$$\operatorname{MEX}$$$ множества чисел — это минимальное целое неотрицательное число, которого нет в множестве, а $$$\operatorname{DIFF}$$$ — количество различных чисел в массиве.
Например, $$$\operatorname{MEX}(\{1, 2, 3\}) = 0$$$, $$$\operatorname{MEX}(\{0, 1, 2, 4, 5\}) = 3$$$.
Вам необходимо определить, какую минимальную стоимость массива $$$a$$$ можно получить, если разрешено сделать не больше $$$k$$$ операций.
В первой строке входных данных находится единственное целое число $$$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$$$ операций.
44 13 0 1 24 10 2 4 57 24 13 0 0 13 1337 10000000006 21 2 8 0 0 0
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$$$ будет $$$[4,\, 13,\, 0,\, 0,\, 13,\, 1,\, 2]$$$, $$$\operatorname{DIFF} = 5$$$, $$$\operatorname{MEX} = 3$$$.
В четвертом наборе входных данных один из возможных массивов $$$a$$$ будет $$$[1,\, 2,\, 3,\, 0,\, 0,\, 0]$$$.
Название |
---|