|
A. Wonderful Permutation
You are given a permutation p1,p2,…,pn of length n and a positive integer k≤n.
In one operation you can choose two indices i and j (1≤i<j≤n) and swap pi with pj.
Find the minimum number of operations needed to make the sum p1+p2+…+pk as small as possible.
A permutation is an array consisting of n distinct integers from 1 to n in arbitrary order. For example, [2,3,1,5,4] is a permutation, but [1,2,2] is not a permutation (2 appears twice in the array) and [1,3,4] is also not a permutation (n=3 but there is 4 in the array).
Input
Each test contains multiple test cases. The first line contains the number of test cases t (1≤t≤100). Description of the test cases follows.
The first line of each test case contains two integers n and k (1≤k≤n≤100).
The second line of each test case contains n integers p1,p2,…,pn (1≤pi≤n). It is guaranteed that the given numbers form a permutation of length n.
Output
For each test case print one integer — the minimum number of operations needed to make the sum p1+p2+…+pk as small as possible.
Example
inputCopy
4
3 1
2 3 1
3 3
1 2 3
4 2
3 4 1 2
1 1
1
outputCopy
1
0
2
0
Note
In the first test case, the value of p1+p2+…+pk is initially equal to 2, but the smallest possible value is 1. You can achieve it by swapping p1 with p3, resulting in the permutation [1,3,2].
In the second test case, the sum is already as small as possible, so the answer is 0.
题目翻译
题目：奇妙的排列
每次测试的时间限制1秒
每次测试的内存限制256 兆字节
输入标准输入
输出标准输出
给你一个排列p1,p2, … ,pn长度n和一个正整数k≤n，
在一项操作中，您可以选择i和j(1 ≤ i < j ≤ n) 并且交换pi和pj.
找出所需的最小操作数使p1+p2+ … +p?尽可能小。
排列是一个由以下组成的数组n不同的整数1至n以任意顺序。例如，[ 2 , 3 , 1 , 5 , 4 ]是一个排列，但是[ 1 , 2 , 2 ]不是排列 (2在数组中出现两次）和[ 1 , 3 , 4 ]也不是排列（n = 3但是还有4在数组中）。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量t(1≤t≤100）。测试用例的描述如下。
每个测试用例的第一行包含两个整数n和?(1≤k≤n≤100）。
每个测试用例的第二行包含n整数p1,p2, … ,pn(1≤pi≤ n）。保证给定的数字形成排列长度为n.
输出
为每个测试用例打印一个整数——求和所需的最小操作数p1+p2+ … +p?尽可能小。
样例
输入
4
3 1
2 3 1
3 3
1 2 3
4 2
3 4 1 2
1 1
1
输出
1
0
2
0
提示
在第一个测试用例中，值为p1+p2+ … +p?最初等于2，但最小的可能值是1. 您可以通过交换来实现它p1和p3，导致排列[ 1 , 3 , 2 ].
在第二个测试用例中，总和已经尽可能小了，所以答案是0.
数据一
Input
4
3 1
2 3 1
3 3
1 2 3
4 2
3 4 1 2
1 1
1
Output
1
0
2
0
数据二
Input
100
11 11
6 10 4 9 11 2 5 8 3 1 7
10 6
1 6 10 2 5 3 9 4 8 7
50 2
20 8 16 46 49 50 26 18 7 38 19 41 39 4 21 29 40 42 1 37 28 35 23 15 43 27 22 47 6 2 14 32 45 9 48 30 36 24 5 11 25 34 13 10 12 44 33 17 3 31
34 21
30 18 20 1 24 23 32 34 9 11 22 21 27 15 7 10 17 6 19 2 26 13 5 33 4 3 8 31 28 14 25 29 12 16
100 39
36 14 49 96 66 17 87 88 58 18 4 95 42 26 23 12 34 31 77 1 60 98 86 78 51 57 16 35 40 6 8 11 93 59 72 82 100 61 43 73 27 37 50 3 10 33 22 62 5 41 55 76 29 91 97 64 2 90 56 38 68 21 15 79 84 …
Output
0
1
2
8
23
9
4
23
13
1
12
2
0
6
22
1
12
9
2
0
1
1
6
11
1
0
3
15
18
2
1
1
17
5
12
10
2
15
1
4
0
2
6
2
15
5
8
21
8
3
2
2
21
9
1
2
4
2
5
0
3
19
0
8
7
0
5
23
7
6
4
3
9
0
13
3
12
10
23
26
1
11
0
1
14
13
1
18
14
7
14
6
0
7
14
6
2
10
1
1
数据三
Input
100
39 38
3 37 35 34 31 13 5 24 7 36 10 14 16 20 8 38 11 26 33 23 15 2 39 27 1 6 17 22 30 9 18 29 25 4 21 12 28 32 19
69 59
9 10 19 38 26 55 4 36 2 1 7 29 45 24 54 8 31 43 23 3 53 64 42 21 57 68 56 44 47 6 30 34 51 13 20 66 12 39 33 58 50 5 32 69 22 46 25 48 28 62 41 37 14 60 63 27 67 35 16 61 17 52 59 15 18 65 49 40 11
66 15
24 15 64 29 4 36 61 32 22 46 26 53 23 27 9 8 11 20 6 18 66 55 33 39 50 17 31 59 10 65 35 2 16 52 56 40 3 43 54 1 7 5 30 21 60 37 38 57 51 34 44 49 25 14 19 12 58 42 41 47 62 63 …
Output
1
8
12
0
1
9
16
23
2
5
2
2
6
3
0
26
6
9
9
10
13
19
0
9
12
13
11
11
17
15
0
10
21
4
18
9
11
8
6
0
14
16
4
24
3
15
3
4
2
13
10
4
16
1
19
3
4
7
2
11
10
10
3
29
13
0
1
14
4
18
18
5
7
1
1
2
1
11
2
8
14
4
12
11
8
11
5
18
15
7
1
7
3
17
8
1
9
12
7
4
数据四
Input
100
59 2
17 48 59 45 36 1 20 14 33 41 7 10 16 34 9 50 4 43 28 15 46 44 30 47 27 53 18 6 51 54 32 13 5 35 29 57 24 49 19 37 11 40 58 39 2 25 22 26 55 21 56 8 3 23 52 42 31 38 12
100 50
59 98 78 88 75 60 35 3 79 84 27 10 96 71 95 38 48 15 62 50 86 32 72 85 90 81 12 17 6 80 67 9 56 5 63 44 46 53 43 40 87 42 47 61 25 45 65 16 69 57 7 64 41 99 74 14 37 55 82 21 31 58 92 70 52 51 23 77 54 30 36 8 94 83 19 26 66 34 28 4 24 91 73 93 49 20 68 13 2 97 11 76 100 22 33 1 89 29 39 18
91 6
24 85 10 65 39 42 83 52 …
Output
2
27
6
1
6
0
2
24
13
10
1
5
8
10
5
11
10
13
31
26
2
13
8
9
11
8
4
10
5
5
1
1
17
20
10
6
18
1
4
12
6
15
10
15
9
19
1
14
6
6
5
0
5
14
13
15
6
17
22
16
4
24
9
0
5
19
7
4
8
0
21
7
0
3
9
9
11
1
3
23
9
15
1
6
7
23
9
10
4
8
2
2
11
2
2
9
9
14
12
0
数据五
Input
100
87 55
47 13 72 22 69 31 55 28 43 79 83 78 29 65 36 4 63 67 59 39 42 14 45 86 6 16 20 8 26 21 1 53 76 73 10 68 18 2 52 15 57 7 27 44 66 48 64 17 24 35 38 77 19 46 80 85 37 32 23 61 82 54 60 33 58 25 81 11 51 71 12 49 40 87 56 3 41 9 30 84 75 5 62 50 70 74 34
67 39
23 55 14 44 4 18 58 57 12 2 13 52 64 41 42 5 25 56 22 36 30 3 27 20 63 7 51 48 39 35 59 29 17 66 45 6 53 65 1 10 31 34 49 11 62 50 26 54 8 16 40 24 9 43 67 33 28 60 38 19 37 47 32 61 15 21 46
78 55
59 62 39 32 13 78 66 26 35 71 74 20 44 …
Output
18
17
16
0
1
1
3
8
7
4
0
9
18
2
12
9
0
8
15
16
7
5
7
1
17
20
21
10
16
8
5
10
8
14
8
4
3
8
23
4
0
6
18
0
6
6
10
21
20
9
24
10
10
3
10
5
16
1
17
3
1
14
3
11
4
11
4
1
4
23
15
17
6
7
17
23
19
20
16
9
0
24
1
3
0
1
9
8
1
1
8
14
0
24
23
14
7
1
1
17
数据六
Input
96
4 1
1 2 3 4
4 2
1 2 3 4
4 3
1 2 3 4
4 4
1 2 3 4
4 1
1 2 4 3
4 2
1 2 4 3
4 3
1 2 4 3
4 4
1 2 4 3
4 1
1 3 2 4
4 2
1 3 2 4
4 3
1 3 2 4
4 4
1 3 2 4
4 1
1 3 4 2
4 2
1 3 4 2
4 3
1 3 4 2
4 4
1 3 4 2
4 1
1 4 2 3
4 2
1 4 2 3
4 3
1 4 2 3
4 4
1 4 2 3
4 1
1 4 3 2
4 2
1 4 3 2
4 3
1 4 3 2
4 4
1 4 3 2
4 1
2 1 3 4
4 2
2 1 3 4
4 3
2 1 3 4
4 4
2 1 3 4
4 1
2 1 4 3
4 2
2 1 4 3
4 3
2 1 4 3
4 4
2 1 4 3
4 1
2 3 1 4
4 2
2 3 1 4
4 3
2 3 1 4
4 4
2 3 1 4
4 1…
Output
0
0
0
0
0
0
1
0
0
1
0
0
0
1
1
0
0
1
1
0
0
1
1
0
1
0
0
0
1
0
1
0
1
1
0
0
1
1
1
0
1
1
1
0
1
1
1
0
1
1
0
0
1
1
1
0
1
1
0
0
1
1
1
0
1
2
1
0
1
2
1
0
1
1
1
0
1
1
1
0
1
1
1
0
1
1
1
0
1
2
1
0
1
2
1
0
数据七
Input
100
10 1
1 2 3 4 5 6 7 8 9 10
10 2
1 2 3 4 5 6 7 8 9 10
10 3
1 2 3 4 5 6 7 8 9 10
10 4
1 2 3 4 5 6 7 8 9 10
10 5
1 2 3 4 5 6 7 8 9 10
10 6
1 2 3 4 5 6 7 8 9 10
10 7
1 2 3 4 5 6 7 8 9 10
10 8
1 2 3 4 5 6 7 8 9 10
10 9
1 2 3 4 5 6 7 8 9 10
10 10
1 2 3 4 5 6 7 8 9 10
10 1
1 2 3 4 5 6 7 8 10 9
10 2
1 2 3 4 5 6 7 8 10 9
10 3
1 2 3 4 5 6 7 8 10 9
10 4
1 2 3 4 5 6 7 8 10 9
10 5
1 2 3 4 5 6 7 8 10 9
10 6
1 2 3 4 5 6 7 8 10 9
10 7
1 2 3 4 5 6 7 8 10 9
10 8
1 2 3 4 5 6 7 8 10 9
1…
Output
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
1
1
0
0
0
0
0
0
0
0
1
1
0
0
0
0
0
0
0
0
1
1
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
1
0
1
0
0
0
0
0
0
0
1
1
0
0
0
0
0
0
0
0
1
1
1
0
代码
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
int num1[110],num2[110];
int main()
{
int t;
cin>>t;
while(t--)
{
int n,k;
cin>>n>>k;
for(int i=0;i<n;i++)
{
cin>>num1[i];
num2[i]=num1[i];
}
sort(num1,num1+n);
int cnt=0;
for(int i=0;i<k;i++)
{
for(int j=0;j<k;j++)
{
if(num1[i]==num2[j])
{
cnt++;
break;
}
}
}
cout<<k-cnt<<endl;
}
return 0;
}
|