← 返回题目列表

Codeforces · 1712/A

A. 精彩排列

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

给你一个长度为 $$$n$$$ 的排列 $$$p_1,p_2,\ldots,p_n$$$ 和一个正整数 $$$k \le n$$$。

在一次操作中,您可以选择两个索引 $$$i$$$ 和 $$$j$$$ ($$$1 \le i < j \le n$$$) 并将 $$$p_i$$$ 与 $$$p_j$$$ 交换。

求使 $$$p_1 + p_2 + \ldots + p_k$$$ 之和尽可能小所需的最少操作数。

排列是一个数组,由 $$$n$$$ 不同的整数组成,从 $$$1$$$ 到 $$$n$$$ 以任意顺序排列。例如,$$$[2,3,1,5,4]$$$ 是一个排列,但 $$$[1,2,2]$$$ 不是排列($$$2$$$ 在数组中出现两次),$$$[1,3,4]$$$ 也不是排列($$$n=3$$$ 但数组中有 $$$4$$$)。

输入

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

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \le k \le n \le 100$$$)。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$p_1,p_2,\ldots,p_n$$$ ($$$1 \le p_i \le n$$$)。保证给定的数字形成长度为 $$$n$$$ 的排列。

输出

对于每个测试用例,打印一个整数 - 使 $$$p_1 + p_2 + \ldots + p_k$$$ 之和尽可能小所需的最少操作数。

示例

输入 #1

4
3 1
2 3 1
3 3
1 2 3
4 2
3 4 1 2
1 1
1

输出 #1

1
0
2
0

注意

在第一个测试用例中,$$$p_1 + p_2 + \ldots + p_k$$$ 的值最初等于 $$$2$$$,但最小可能值为 $$$1$$$。您可以通过将 $$$p_1$$$ 与 $$$p_3$$$ 交换来实现,从而得到排列 $$$[1, 3, 2]$$$。

在第二个测试用例中,总和已经尽可能小,因此答案是 $$$0$$$。