PAT 甲级 1067 Sort with Swap(0, i) (25 分) 代码10分钟，bug 1晚上+1小时果然还是状态最重要

电玩女神 2024-02-19 21:54 9阅读 0赞

## 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 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<iostream>
    #include<cstdio>
    #include<map>
    using namespace std;
    int main()
    {
    	int n,i,j,t,cnt=0;
    	int zero_index;
    	map<int,int> a;
    	int b[100005];
    	cin>>n;
    	for(i=0;i<n;i++)
    	{
    		cin>>b[i];
    		if(b[i]==0)
    		zero_index=i;
    		if(b[i]!=i&&b[i]!=0)       // 把跟下标不对应的单元，放进map 
    		a.insert(make_pair(b[i],i));
    	}
        if(b[0]==0&&a.size()>0)      // 这个是防止 这组数据 9    0 2 1 4 3 6 5 8 7  第一个0使cnt加了两次 
        cnt=-1;
    	while(a.size()!=0)
    	{
    		b[a[zero_index]]=0;
    		b[zero_index]=zero_index;
    		t=zero_index;
    		zero_index=a[zero_index];
    		a.erase(a.find(t));
    		if(b[0]==0&&a.size()>0)    // 这是为了防止出现0号单元的值是0，但是还未有序   ，需要找一个数交换0 
    		{
    			int temp=a.begin()->first;
    			int index=a.begin()->second;
            	b[0]=temp;
    			b[index]=0;
    			a.erase(a.find(temp));
    			zero_index=index;
    			a.insert(make_pair(temp,0));
    			cnt++;
    		}
    		cnt++;
    	}
    	cout<<cnt<<endl;
    	return 0;
    }