1067. Sort with Swap(0,*) (25)

怼烎@ 2022-05-30 00:45 111阅读 0赞

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 N nonnegative integers.

**Input Specification:**

Each input file contains one test case, which gives a positive N (<=105) 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:**

--------------------

题目大意：

代码：

#include<stdio.h>
    #include<map>
    using namespace std;
    map<int,int> Map;
    int main()
    {
        int i,j,n,m,k,t,flag,cnt,num=0,index=1;
        scanf("%d",&n);
        for(i=0;i<n;i++)
        {
            scanf("%d",&m);
            if(m!=i)
                num++;
            Map[m]=i;
        }
        cnt=0;
        while(num>1)
        {
            //printf("%d %d\n",cnt,num);
         if(Map[0]==0)
         {
             while(index < n) 
                {
                    if(Map[index] != index) 
                    {
                        Map[0]=Map[index];
                        Map[index]=0;
                        cnt++;
                        break;
                    }
                    index++;
                }
         }
               while(Map[0]!=0)
               {
                   int index0=Map[0];
                   int index1=Map[index0];
                   Map[0]=index1;
                   Map[index0]=index0;
                   cnt++;
                   num--;
               }
        }
        printf("%d\n",cnt);
        return 0;
    }