交换

链接：https://ac.nowcoder.com/acm/contest/5773/E
来源：牛客网

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld
题目描述
牛客幼儿园的小朋友课间操时间需要按照学号从小到大排队，但是他们太小了只能站成一列顺序却不对，现在幼儿园的阿姨需要帮忙交换小朋友的位置让他们最终有序，阿姨希望能尽快完成交换操作，问最少需要交换多少次，才能使得小朋友们从小到大排好。
注意：每个小朋友的学号不同，但是未必连续，因为可能有小朋友请假了没有来。
输入描述:
第一行一个整数 N。
接下来 N 行每行一个整数，为小朋友们的队列。
输出描述:
一个整数表示小朋友们的最小交换次数。
示例1
输入
3
2
1
3

输出
1
备注:
N<100000，其他整数均≤10^9

题解：
由于是随机排序，所以不妨先从复杂的考虑，为了使得交换次数最少，而交换又是随机的，要尽可能少步骤的排完序。所以不用逆序对，而用选择排序，使得先把最小的放到第一个位置，再把次小的放到第二个位置，复杂度o(n^2)，最多交换n-1次。显然是过不了的，但思维没有问题。
接下来就是考虑如何空间换时间了。最大承受复杂度在o(nlogn)。我们先用sort造出一个有序数组表示换的最终结果和另一个判断是否交换的数组，接着考虑每次交换发生了什么。有两种情况分别是交换环和不交换。
举个例子： 原数组： 3 2 6 4 1
交换后： 1 2 3 4 6
可以发现第二位和第四位是天然不须交换的。而3，6，1与交换后1，3，6形成了一个环状交换（有两个元素相互交换就有序的情况也可以认为是环的哦）。那么就需要在这个环当中交换两次变回顺序。而非环部分则不需要变换。
进一步考虑，我们所谓的非环部分不也可以认为是一个长度为0的一个环吗？这样就对数据统计进行了统一。
我们通过判断数组就很容易求出这些数据一共形成几个环，交换次数经简单计算就可得出为：n-环数。（这里我其实是讨巧，环为n的时候不需要交换）
这样只有排序为o(nlogn),其他都是o(n)复杂度，综合复杂度o(nlogn)。

代码：
#include<bits/stdc++.h>
using namespace std;
int v[1000005],v1[1000005],flag[1000005];
int n,k;
int Min_Swaps()
{
for (int i=0;i<n;i++)
{
v1[i]=v[i]; //将A内元素复制到B。
}
sort(v1,v1+n);
map<int,int> m;
for (int i=0;i<n;i++)
{
m[v1[i]]=i; // 建立每个元素与其应放位置的映射关系
}
int num=0; // 循环节个数
//找出循环节的个数
for (int i=0;i<n;i++)
{
if (!flag[i])
{
int j=i;
while (!flag[j]) //对环处理
{
flag[j]=true;
j=m[v[j]]; //原序列中j位置的元素在有序序列中的位置
}
num++;
}
}
return n-num;
}
int main()
{
cin>>n;
for (int k=0;k<n;k++)
{
cin>>v[k];
}
int ans=Min_Swaps();
cout<<ans;
return 0;
}