记录编号	336695	评测结果	AAAAAAAAAA
题目名称	[焦作一中2012] 最小交换排序(无数据)	最终得分	100
用户昵称	SOBER GOOD BOY	是否通过	通过
代码语言	C++	运行时间	0.448 s
提交时间	2016-11-03 17:21:32	内存使用	1.46 MiB

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>

using namespace std;

const int maxn=100000+100;

struct node
{
  int data,pos1,pos2;
}A[maxn];

bool compdata(node a,node b)
{return a.data<b.data;}

bool comppos(node a,node b)
{return a.pos1<b.pos1;}

int N,Ans=0;

int main()
{
    freopen("minsort.in","r",stdin); 
    freopen("minsort.out","w",stdout);
    scanf("%d",&N);
    for(int i=1;i<=N;i++)
    scanf("%d",&A[i].data),A[i].pos1=i;
    sort(A+1,A+N+1,compdata);
    for(int i=1;i<=N;i++)
    A[i].pos2=i;
    sort(A+1,A+N+1,comppos);
     int la=999;
     while(1)
     {
         la=Ans;    
         for(int i=1;i<=N;i++)
         {
           if(A[i].pos2!=i)
           swap(A[A[i].pos2],A[i]),Ans++;
         }    
         if(Ans==la)break;
     }
     printf("%d",Ans);
    return 0;
}