P1327 数列排序

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+10;
struct px{
	int x;
	int y;
};
px a[N];
int b[N],n,ans;

bool bmp(px a1,px a2){
	return a1.x<a2.x;
}

int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i].x;
		b[i] = a[i].x;
		a[i].y = i;
	}
	sort(a+1,a+n+1,bmp);
	for(int i=1;i<=n;i++){
		if(b[i]!=a[i].x){
			int tmp = b[i];
			swap(b[i],b[a[i].y]);
			ans++;
			int t=i+1;
			while(a[t].x!=tmp)t++;
			a[t].y = a[i].y;
			a[i].y = i;
		}
	}
	cout<<ans;
	return 0;
}