← 返回题目列表

Codeforces · 2085/F1

F1. 薮猫和七彩阵(简单版)

中文机器翻译题面 查看原题

这是问题的简单版本。版本之间的区别在于,在这个版本中,$$$n\le 3000$$$。只有解决了该问题的所有版本,您才能破解。

Serval 有一个神奇的数字 $$$k$$$ ($$$k\ge 2$$$)。我们称数组为$$$r$$$ 多彩 当且仅当:

  • $$$r$$$ 的长度为 $$$k$$$,并且
  • $$$1$$$ 和 $$$k$$$ 之间的每个整数出现 正好一次 在$$$r$$$。

给定一个数组 $$$a$$$,由 $$$1$$$ 和 $$$k$$$ 之间的 $$$n$$$ 整数组成。保证 $$$1$$$ 和 $$$k$$$ 之间的每个整数在 $$$a$$$ 中至少出现一次。您可以对$$$a$$$执行以下操作:

  • 选择一个索引 $$$i$$$ ($$$1\le i \lt n$$$),然后交换 $$$a_i$$$ 和 $$$a_{i+1}$$$。

求至少生成一个 $$$a$$$ 子数组$$$^{\text{∗}}$$$ 所需的最少操作数 多彩。可以证明,在问题的约束下这总是可能的。

$$$^{\text{*}}$$$数组 $$$b$$$ 是数组 $$$a$$$ 的子数组,如果 $$$b$$$ 可以通过从 $$$a$$$ 删除开头的几个(可能是零个或全部)元素和从末尾删除几个(可能是零个或全部)元素来获得。

输入

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

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$2\leq k\leq n\leq 3000$$$) — 数组 $$$a$$$ 的长度和 Serval 的幻数。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1\leq a_i\leq k$$$) — 数组 $$$a$$$ 的元素。保证 $$$1$$$ 和 $$$k$$$ 之间的每个整数在 $$$a$$$ 中至少出现一次。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$3000$$$。

输出

对于每个测试用例,输出一个整数 - 生成至少一个 $$$a$$$ 子数组所需的最少操作数 多彩.

示例

输入
复制

6
3 2
1 2 1
7 3
2 1 1 3 1 1 2
6 3
1 1 2 2 2 3
6 3
1 2 2 2 2 3
10 5
5 1 3 1 1 2 2 4 1 3
9 4
1 2 3 3 3 3 3 2 4

输出
复制

0
1
2
3
4
5

注意

在第一个测试用例中,由于子数组 $$$[a_1, a_2] = [1, 2]$$$ 和 $$$[a_2, a_3] = [2, 1]$$$ 已经 多彩,我们不需要执行任何操作。因此,答案是$$$0$$$。

在第二个测试用例中,我们可以交换 $$$a_1$$$ 和 $$$a_2$$$ 得到 $$$[1, \underline{2, 1, 3}, 1, 1, 2]$$$,它有一个 多彩 子数组 $$$[a_2, a_3, a_4] = [2, 1, 3]$$$。并且给定的数组最初没有任何 多彩 子数组,所以答案是 $$$1$$$。