Problem Description
Kayaking is playing a puzzle game containing n different blocks. He marks the blocks with integers from 1 to n, which show the blocks’ original positions. Each time he can exchange two blocks and he wants to know how many times he needs at least to restore the puzzle.
Input
The input starts with one line contains exactly one
positive integer which is the number of test cases.
Each test case contains
two lines.
The first line contains an integer, which indicates the number of
puzzle pieces.
The second line contains n different integers, the i-th number
means the mark of the block in the i-th position.
positive integer which is the number of test cases.
Each test case contains
two lines.
The first line contains an integer, which indicates the number of
puzzle pieces.
The second line contains n different integers, the i-th number
means the mark of the block in the i-th position.
Output
For each test case, output one line with one number
represents the minimum operations.
represents the minimum operations.
Sample Input
2
4
2 3 4 1
4
2 1 4 3
4
2 3 4 1
4
2 1 4 3
Sample Output
3
2
2
Hint
1<=T<=20,1<=n<=100000
题意：有顺序不定的从1到n的n个数，排序，每次操作更换两个数的位置，求最少操作次数，使得排序为从变成从 1 到 n。
思路：标记每个数应该所在的位置，然后将该位置上的数寻找其应有的位置并进行标记，并标记好每个数位置是否已经找好。具体看代码注释
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
const int N = 1e6+10;
int a[N],vis[N]; //vis数组记录每个数是否找过他应该在的位置
int main()
{
int t;
scanf("%d",&t);
while(t--){
memset(vis,0,sizeof(vis));
int ans = 0;
int n,i;
scanf("%d",&n);
for(i = 1; i <= n; i++){
scanf("%d",&a[i]);
}
for(i = 1; i <= n; i++){
int temp = a[i],x = 0;
while(!vis[temp]){ //temp 还没找过其应在的位置
vis[temp] = 1; //标记temo已经找过
temp = a[temp]; //用temp应在的位置上的数覆盖temp，如果其在应在的位置那么继续while循环直接跳出然后不用做交换
x++;
}
if(x > 0){
ans += x-1; //遍历每一组情况下应该对x减一才能得到正确的交换次数
}
}
printf("%d\n",ans);
}
return 0;
}