清空数组AI (CI翻译)
You are given an array $a$ of length $n$ and an integer $k$.
给定一个长度为 $n$ 的数组 $a$ 和一个整数 $k$。AI (CI翻译)
In one operation, choose any element $x$ of the array.
每次操作，你可以选择数组中的任意一个元素 $x$。AI (CI翻译)
- If
$x \le k$, erase$x$from the array. - Otherwise, erase
$x$and insert two elements equal to$\left\lceil \dfrac{x}{2} \right\rceil$.
- 如果
$x \le k$，则从数组中删除$x$。 - 否则，删除
$x$，并插入两个值均为$\left\lceil \dfrac{x}{2} \right\rceil$的元素。
In both cases, increase $k$ by $1$ after performing the operation.
在两种情况下，执行操作后都将 $k$ 增加 $1$。AI (CI翻译)
Find the minimum number of operations required to make the array empty.
求清空数组所需的最少操作次数。AI (CI翻译)
Input
输入格式
AI (CI翻译)Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.
每组输入包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10^4$）。接下来是各个测试用例的描述。AI (CI翻译)
The first line of each test case contains two integers $n$ and $k$ ($1 \le n \le 2 \cdot 10^5$, $0 \le k \le n$) — the length of the array and the initial value of $k$.
每个测试用例的第一行包含两个整数 $n$ 和 $k$（$1 \le n \le 2 \cdot 10^5$，$0 \le k \le n$）——分别表示数组的长度和 $k$ 的初始值。AI (CI翻译)
The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le n$) — the elements of the array.
第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le n$）——表示数组中的元素。AI (CI翻译)
It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.
保证所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$。AI (CI翻译)
Output
输出格式
AI (CI翻译)For each test case, output a single integer — the minimum number of operations required to make the array empty.
对于每个测试用例，输出一个整数——清空数组所需的最少操作次数。AI (CI翻译)
Note
说明
AI (CI翻译)In the first example, initially $k = 0$. We can perform the following operations:
在第一个样例中，初始时 $k = 0$。我们可以执行以下操作：AI (CI翻译)
- Split an element equal to
$4$into two elements equal to$2$;$k$becomes$1$. - Erase an element equal to
$1$;$k$becomes$2$. - Erase an element equal to
$2$;$k$becomes$3$. - Erase an element equal to
$2$;$k$becomes$4$. - Erase an element equal to
$4$;$k$becomes$5$. - Erase an element equal to
$4$;$k$becomes$6$.
- 将一个值为
$4$的元素拆分成两个值为$2$的元素；$k$变为$1$。 - 删除一个值为
$1$的元素；$k$变为$2$。 - 删除一个值为
$2$的元素；$k$变为$3$。 - 删除一个值为
$2$的元素；$k$变为$4$。 - 删除一个值为
$4$的元素；$k$变为$5$。 - 删除一个值为
$4$的元素；$k$变为$6$。
The array becomes empty after $6$ operations.
经过 $6$ 次操作后，数组变为空。AI (CI翻译)
In the fourth example, initially $k = 2$. We can perform the following operations:
在第四个样例中，初始时 $k = 2$。我们可以执行以下操作：AI (CI翻译)
- Split an element equal to
$6$into two elements equal to$3$;$k$becomes$3$. - Erase an element equal to
$3$;$k$becomes$4$. - Erase an element equal to
$3$;$k$becomes$5$. - Erase an element equal to
$5$;$k$becomes$6$. - Erase an element equal to
$6$;$k$becomes$7$. - Erase an element equal to
$6$;$k$becomes$8$. - Erase an element equal to
$6$;$k$becomes$9$. - Erase an element equal to
$6$;$k$becomes$10$.
- 将一个值为
$6$的元素拆分成两个值为$3$的元素；$k$变为$3$。 - 删除一个值为
$3$的元素；$k$变为$4$。 - 删除一个值为
$3$的元素；$k$变为$5$。 - 删除一个值为
$5$的元素；$k$变为$6$。 - 删除一个值为
$6$的元素；$k$变为$7$。 - 删除一个值为
$6$的元素；$k$变为$8$。 - 删除一个值为
$6$的元素；$k$变为$9$。 - 删除一个值为
$6$的元素；$k$变为$10$。
The array becomes empty after $8$ operations.
经过 $8$ 次操作后，数组变为空。AI (CI翻译)
样例
8
4 0
4 4 1 4
3 0
3 2 2
6 3
6 3 6 4 6 5
6 2
6 6 5 6 6 6
5 0
3 5 3 1 3
6 1
6 4 6 5 4 6
7 1
7 2 7 7 3 7 7
8 0
8 8 2 8 8 1 8 8
6
5
6
8
7
8
11
12
题面与样例版权归 Codeforces 及出题人所有；中文翻译由 AI 生成（gpt-6.1-sol），如有出入请以原文为准。