題目描述
有N個(gè)瓶子着绷，編號(hào) 1 ~ N，放在架子上销部。
比如有5個(gè)瓶子：2 1 3 5 4硫椰，要求每次拿起2個(gè)瓶子，交換它們的位置骆莹。
經(jīng)過若干次后颗搂，使得瓶子的序號(hào)為：1 2 3 4 5
對(duì)于這么簡單的情況，顯然幕垦，至少需要交換2次就可以復(fù)位丢氢。
如果瓶子更多呢傅联？你可以通過編程來解決。
輸入
輸入存在多組測試數(shù)據(jù)疚察，對(duì)于每組測試數(shù)據(jù)：
第一行: 一個(gè)正整數(shù)N（N<10000）, 表示瓶子的數(shù)目
第二行：N個(gè)正整數(shù)蒸走，用空格分開，表示瓶子目前的排列情況貌嫡。
輸出
對(duì)于每組測試數(shù)據(jù)輸出一行比驻，包含一個(gè)正整數(shù)表示答案
樣例輸入
5
3 1 2 5 4
5
5 4 3 2 1
樣例輸出
3
2
代碼
#include<iostream>
#include<ctime>
#include<cmath>
#include<bits/stdc++.h>
int a[10010],b[10010];
using namespace std;
int main(){
int n,sum;
while(cin>>n){
sum=0;
for(int i=1;i<=n;i++){
cin>>a[i];
b[a[i]]=i;
}
for(int i=1;i<=n;i++){
//如果自身位置的數(shù)和編號(hào)對(duì)的上就跳過
if(a[i]==i)
continue;
//不行則交換
int pos1=i,num1=a[i];
int pos2=b[i],num2=i;
sum++;
a[pos2]=num1;
b[num1]=pos2;
a[pos1]=num2;
b[num2]=pos1;
}
cout<<sum<<endl;
}
return 0;
}
