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 (≤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
百度了一下，发现现有的方法都是swap进行模拟操作，才知道swap可以用于交换，我的有点不同。
我这个题的思想是，根据一个数 ，比如样例的下标为9的数是1，那么就找到下标为1的数是5，然后下标是5的数是4，然后就一直这样找下去，最终会形成一个环，理想的情况是0不在0的位置，并且在这个环里面，那么只要去除那些本来就在原来位置的（这些不用再swap），环的长度-1就是我们要交换的次数。如果0在0的位置，要打破一个封闭的环，比如（小标为1，2的数值）2，1要变成1，2，首先要用在0下标位置的0与1或者2交换，最终又要再回到0位置，那么这时候需要对总体次数+2.
#include<iostream>
#include<vector>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<set>
using namespace std;
const int maxn=1e5+20;
int a[maxn],vis[maxn];void search(int r)
{vis[r]=1;// cout<<"r:"<<r<<endl;if(!vis[a[r]]){search(a[r]);}
}int main()
{int n;cin>>n;int ans=0;int pos0;int cnt=0;for(int i=0;i<n;i++){scanf("%d",&a[i]);if(a[i] == i){cnt++;vis[i]=1;}// 本来就在原来的位置的数 cnt计数，并且不参与封闭环计数}if(a[0] == 0){ans=ans+2; //让0进入某个环，这样的话以下皆以0不在0位置考虑}int circle=0; // 封闭环的个数for(int i=0;i<n;i++){if(!vis[i]){search(a[i]);circle++; //破开一个环需要一次 交换0数值，将两个环连接起来}}cout<<n-cnt-1+circle-1+ans; // n-cnt-1是正常理想情况下，0不在0位置，只有一个环的计算
//+ans是将0放入到环中， circle-1是需要连接多少次，将所有环连城一个return 0;
}