A1763.奇妙的排列

入门

通过率:0%

时间限制:1.00s

内存限制:128MB

题目描述

给定一个 nn 的全排列 aia_ikk。(1in1 \le i \le na1a_1~ana_nnn 的一个全排列)。

在一次操作中,可以选择两个下标 iijj,交换 aia_iaja_j。(1i<jn1 \le i < j \le n)

求出使 i=1k\sum_{i=1}^{k} aia_i 最小所需要的最少操作次数。(i=1k\sum_{i=1}^{k} aia_i =a1+a2......+ak= a_1 + a_2 ......+ a_k

输入格式

第一行包含测试用例的数量 TT (1T1001 \le T \le 100)。

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

每个测试用例的第二行包含 nn 个整数 a1a_1~ana_n

输出格式

对于每个测试用例打印一个整数,表示使 i=1k\sum_{i=1}^{k} aia_i 最小所需要的最少操作次数。

输入输出样例

  • 输入#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

说明/提示

在第一个测试用例中,交换 a1a_1a3a_3,序列为 1 3 2i=11\sum_{i=1}^{1} aia_i 最小,为 11,交换次数为 11

在第二个测试用例中,i=13\sum_{i=1}^{3} aia_i 已经是最小了,交换次数为 00

首页