• Codeforces Round #813 (Div. 2) A. Wonderful Permutation


    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

    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 
    #include 
    #include 
    #include 
    #include 
    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;
    }
    
    
  • 相关阅读:
    摊还分析在算法设计中的应用
    java面试宝典2019
    python学习随笔3
    【洛谷 P1012】[NOIP1998 提高组] 拼数 题解(贪心算法+字典序排序)
    Docker 搭建 Minio 容器
    通过Python脚本支持OC代码重构实践(二):数据项提供模块接入数据通路的代码生成
    绑定样式--class样式(字符串法、对象法、数组法)、style样式(直接绑定法、对象法、数组法)
    【Java面试】面试如何让面试官面的很爽,看完这道面试题,finally块一定会执行吗?
    【Swift 60秒】05 - String interpolation
    C/C++中如何让程序接受并处理命令行参数
  • 原文地址:https://blog.csdn.net/wyyyyyyyy_/article/details/127037112