A1067 Sort with Swap(0, i) (25 分)

一、技术总结

1. 题目要求是，只能使用0,进行交换位置，然后达到按序排列，所使用的最少交换次数
2. 输入时，用数组记录好每个数字所在的位置。
3. 然后使用for循环，查看i当前位置是否为该数字，核心是等待0回到自己的位置上，如果没有一直与其他的数字进行交换。如果这个过程中，i回到自己位置上就不用调换，如果不是那么直接与0位置进行调换，直到所有位置都到指定位置上面。

二、参考代码

#include<iostream>
#include<algorithm>
using namespace std;
int main(){
	int n, ans = 0, a[100010], t;
	cin >> n;
	for(int i = 0; i < n; i++){
		cin >> t;
		a[t] = i;
	}
	for(int i = 1; i < n; i++){
		if(i != a[i]){
			while(a[0] != 0){
				swap(a[0], a[a[0]]);
				ans++;
			}
			if(i != a[i]){
				swap(a[0], a[i]);
				ans++;
			}
		}
	}
	cout << ans;
	return 0;
	
}