交换-2020年牛客算法入门课练习赛1

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

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

有个隐藏条件，因为是学号，所以不会有相同数字。
任意两数都可以交换位置，最多交换n-1次就能有序。
这是一个查找问题，定义a数组为原有序列，b数组为排序之后序列，如果a和b同一位置数字相同不交换，ai和bi不相同我们要在a中找到bi的位置，然后交换。因此提前用map记录好每个值在a数组中的下标。注意交换后要更新map中位置信息。

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
int a[100005],b[100005],n;
map<int,int>m1;
int main()
{
    ios::sync_with_stdio(0),cin.tie(0);
    int i,j,ans=0;
    cin>>n;
    for(i=1;i<=n;i++)
    {
        cin>>a[i];
        m1[a[i]]=i; /**< 记录下每个值的具***置，方便后面查找 */
        b[i]=a[i];
    }
    sort(b+1,b+n+1);
    for(i=1;i<=n;i++)
    {
        if(b[i]!=a[i]) /**< 需要交换，第i个位置应该是b[i] */
        {
            m1[a[i]]=m1[b[i]]; /**< a[i]的位置换到a数组中b[i]哪里 */
            swap(a[i],a[m1[b[i]]]); /**< a数组两值交换 */
            ans++;
        }
    }
    cout<<ans<<endl;
    return 0;
}