1067 Sort with Swap(0, i) （25 分）

时间：2022-02-21 20:04:15
1067 Sort with Swap(0, i) （25 分）

Given any permutation of the numbers {0, 1, 2,..., N−1}, it is easy to sort them in increasing order. But what if Swap(0, *) is the ONLY operation that is allowed to use? For example, to sort {4, 0, 2, 1, 3} we may apply the swap operations in the following way:

Swap(0, 1) => {4, 1, 2, 0, 3}
Swap(0, 3) => {4, 1, 2, 3, 0}
Swap(0, 4) => {0, 1, 2, 3, 4}

Now you are asked to find the minimum number of swaps need to sort the given permutation of the first Nnonnegative integers.

Input Specification:

Each input file contains one test case, which gives a positive N (≤10​5​​) followed by a permutation sequence of {0, 1, ..., N−1}. All the numbers in a line are separated by a space.

Output Specification:

For each case, simply print in a line the minimum number of swaps need to sort the given permutation.

Sample Input:

10
3 5 7 2 6 4 9 0 8 1

Sample Output:

9

题意：输入一个序列，如果某个数不在该位置，比如1不在1号位，那么需要和0交换，直到整个序列都在数所对应的位置上，过程中只能用0交换，求最小交换次数

分析：贪心题，要次数最小，只要每次和0交换后到达所对应的位置，简单地说就是换一次就不用再换了。这里要考虑两种情况，第一种是0不在0号位，那么找到0在的位置，比如在3号位，那么和三号位对应的数交换；第二种是0在0号位，找到第一个不在本位上的数交换。

为了方便起见，数组用来存数的位置。如下所示：
t 4 1 2 0 3
a[] 3 1 2 4 0 
 
 /**
 * Copyright(c)
 * All rights reserved.
 * Author : Mered1th
 * Date : 2019-02-26-10.19.41
 * Description : A1067
 */
 #include<cstdio>
 #include<cstring>
 #include<iostream>
 #include<cmath>
 #include<algorithm>
 #include<string>
 #include<unordered_set>
 #include<map>
 #include<vector>
 #include<set>
 using namespace std;
 ;
 int main(){
 #ifdef ONLINE_JUDGE
 #else
     freopen("1.txt", "r", stdin);
 #endif
     },num=;
     scanf("%d",&n);
     ;
     ;i<n;i++){
         scanf("%d",&t);
         a[t]=i;
         ) left--;
     }
     ;
     while(left){
         int i;
         ]==){
             for(;j<n;j++){
                 if(a[j]!=j){
                     swap(a[j],a[]);
                     num++;
                     break;
                 }
             }
         }
         else{
             swap(a[],a[a[]]);
             num++;
             left--;
         }

     }
     cout<<num;

     ;
 }
 

相关文章