← 返回题目列表

Codeforces · 2157/E

E. 调整无人机

中文机器翻译题面 查看原题
PIXL - 这次
⠀

您正在管理一支由 $$$n$$$ 无人机组成的机队,每架无人机的能量级别为 $$$a_1、\ldots、a_n$$$。您还会获得一个正整数 $$$k$$$,它表示允许共享相同能量水平的无人机的最大数量。

为了防止过载,无人机自动执行如下能量平衡操作。虽然存在严格出现超过 $$$k$$$ 次的能量水平,但它们执行以下步骤:

  • 首先,标记每架能量$$$a_i$$$出现较早的无人机$$$i$$$(即存在$$$j \lt i$$$且$$$a_j = a_i$$$);
  • 然后,对于每架被标记的无人机,其能量增加$$$1$$$单位;
  • 然后,标记被移除。

一旦没有能量水平出现超过 $$$k$$$ 次,该过程就会停止。确定将执行多少能量平衡操作。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。

每个测试用例的第一行包含两个整数 $$$n$$$、$$$k$$$ ($$$1 \leq k \leq n \leq 2 \cdot 10^5$$$) — 无人机数量以及具有相同能量级别的最大允许无人机数量。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 2n$$$) — 无人机的初始能量水平。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,输出一行包含一个整数:执行的能量平衡操作的数量。

示例

输入
复制

5
6 3
1 1 1 1 1 1
5 1
1 3 2 1 4
6 2
1 1 1 2 3 3
4 1
8 8 8 8
2 2
1 2

输出
复制

3
4
4
3
0

注意

在第一个测试用例中,无人机的能量水平演变如下:

  • 开头,$$$[1, 1, 1, 1, 1, 1]$$$;
  • $$$1$$$ 操作后,$$$[1, 2, 2, 2, 2, 2]$$$;
  • $$$2$$$ 操作后,$$$[1, 2, 3, 3, 3, 3]$$$;
  • $$$3$$$ 操作后,$$$[1, 2, 3, 4, 4, 4]$$$。

经过$$$3$$$操作后,每个能量级别最多出现$$$3$$$次,因此该过程停止。

在第二个测试用例中,能级变化如下: $$$[1, 3, 2, 1, 4] \rightarrow [1, 3, 2, 2, 4] \rightarrow [1, 3, 2, 3, 4] \rightarrow [1, 3, 2, 4, 4] \rightarrow [1, 3, 2, 4, 5]$$$。该过程在 $$$4$$$ 操作后停止。