“新智认知”杯上海高校程序设计竞赛暨第十七届上海大学程序设计春季联赛 E CSL 的魔法

“新智认知”杯上海高校程序设计竞赛暨第十七届上海大学程序设计春季联赛 E CSL 的魔法

题目链接：

来源牛客网

显然我们可以先排序，此题最好用结构体排，用map会tle，亲测真心疼。。。

通过这一次排序，也就是通过最后的结束情况，知道原始a数组中的数与b数组中的数的对应关系

通过观摩大佬的代码，深刻感受到了与大佬的差距之大，哎。。。

回归题目，显然我们无异于数组元素值，我们关注的是他们在各自数组中的大小顺序和对应关系。大佬用一个for和一个while征服了我，简洁完美地实现了交换，在交换地过程中压根就没碰开始的那个a,b数组，却又实实在在地模拟了交换，膜......

#include <bits/stdc++.h>using namespace std;struct number
{int n;int id;
};
number a[100005];
number b[100005];
int vis[100005];
bool cmp(number a,number b)
{return a.n<b.n;
}bool cmp2(number a,number b){return a.n>b.n;}
int main()
{int num;scanf("%d",&num);for(int i=0; i<num; i++){scanf("%d",&a[i].n);a[i].id=i;}for(int i=0; i<num; i++){scanf("%d",&b[i].n);b[i].id=i;}sort(a,a+num,cmp);sort(b,b+num,cmp2);for(int i=0;i<num;i++){vis[a[i].id]=b[i].id;   //确定a,b对应位置}int sum=0;for(int i=0;i<num;i++){int tp=i,res=0;while(tp!=vis[tp]){int tx=tp;tp=vis[tp];vis[tx]=tx;         //交换位置res++;}if(res)sum+=(res-1);       //按照上面的交换方法，如果交换，最后肯定和之前的有一次重合，所以减一}cout<<sum<<endl;
}