数列排序题解

看到这道题，我不由地想起了在CSP-J初赛的一道题：
对于下列数列，最少需要交换几次才能变成升序……

解题思路
既然这样，我们知道每个数在最后都有唯一的位置，那用贪心+模拟就可以解决

但是你怎么提前知道这个数最终的排名呢？
其实，我们发现，这个交换排序的过程是可以反过来变成一个有序的数列，如何变成给出的数列
既然这样，我们用结构体存储每一项的值和初始下标，然后对数组排序，最后再暴力模拟交换的过程就可以了

模拟过程
显然这道题涉及交换，所以不能直接简单for循环过
我们设立一个变量idx用来存储当前查询的元素下标（注意和结构体的原下标做区分）
只有当前值满足条件（等于原来的值）才往后加
当不满足条件时，将另一个答案数组sum++,然后交换目标元素

注意事项
如果自己手写排序的可以跳过，但作者用了sort，快排不稳定，所以在后面判断时要注意别漏了值相等的情况也不用交换

最后奉上AC代码

#include<iostream>
#include<algorithm>
using namespace std;
int n;
struct num{
	int n,id;
}a[100005];
bool cmp(num x,num y){
	return x.n<y.n;
}
int main(){
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>a[i].n;
		a[i].id=i;
	}
	sort(a,a+n,cmp);
	int sum=0,idx=0;
	while(idx<n){
		if(a[idx].id==idx || a[a[idx].id].n==a[idx].n){
			idx++;
			continue;
		}
		swap(a[idx],a[a[idx].id]);
		sum++;
	}
	cout<<sum;
}//作者不爱写return 0;