leetcode-634 Find the Derangement of An Array（水水的模拟）

深藏阁楼爱情的钟 2022-06-11 09:06 144阅读 0赞

Given an array containing a permutation of **1** to **n**, you have to find the minimum number of swaps to sort the array in ascending order. A swap means, you can exchange any two elements of the array.

For example, let **n = 4**, and the array be **4 2 3 1**, then you can sort it in ascending order in just **1** swaps (by swapping **4** and **1**).

Input

Input starts with an integer **T (≤ 100)**, denoting the number of test cases.

Each case contains two lines, the first line contains an integer **n (1 ≤ n ≤ 100)**. The next line contains **n** integers separated by spaces. You may assume that the array will always contain a permutation of **1** to **n**.

Output

For each case, print the case number and the minimum number of swaps required to sort the array in ascending order.

Sample Input

4 2 3 1

4 3 2 1

1 2 3 4

Sample Output

Case 1: 1

Case 2: 2

Case 3: 0

题解：

直接模拟全过程就好了

代码：

#include<algorithm>
    #include<iostream>
    #include<cstring>
    #include<stdio.h>
    #include<math.h>
    #include<string>
    #include<stdio.h>
    #include<queue>
    #include<stack>
    #include<map>
    #include<deque>
    #define M (t[k].l+t[k].r)/2
    #define lson k*2
    #define rson k*2+1
    using namespace std;
    int a[105];
    int b[105];
    int main()
    {
        int i,j,k,ans,num=1,n,t,c;
        scanf("%d",&t);
        while(t--)
        {
            scanf("%d",&n);
            c=0;
            ans=0;
            for(i=0;i<n;i++)
            {
                scanf("%d",&a[i]);
                b[i]=a[i];
            }
            sort(b,b+n);
            for(i=0;i<n;i++)//对照排序以后的来模拟交换
            {
                if(a[i]==b[i])
                    continue;
                for(j=i+1;j<n;j++)
                {
                    if(a[j]==b[i])
                    {
                        swap(a[i],a[j]);
                        c++;
                        break;
                    }
                }
            }
            printf("Case %d: %d\n",num,c);
            num++;
        }
        return 0;
    }