首页 > 代码库 > 51nod 1574 排列转换
51nod 1574 排列转换
分析：
大佬们也有搞错的时候，说把s重排一下，求逆序数对就行了； 这个是相邻两两交换；
正解：
是将所有没有在正确位置的数，他们一次性到达他正确的位置，没有浪费；
1 #include <bits/stdc++.h> 2 3 using namespace std; 4 5 const int maxn = 200000 + 5; 6 int a[maxn]; 7 int b[maxn]; 8 bool vis[maxn]; 9 10 int main()11 {12 int n;13 scanf("%d",&n);14 15 memset(vis,0,sizeof(vis));16 17 for(int i=0;i<n;i++)18 scanf("%d",&a[i]);19 20 for(int i=0;i<n;i++) {21 int tmp;22 scanf("%d",&tmp);23 b[tmp] = i;24 }25 26 for(int i=0;i<n;i++) {27 a[i] = b[a[i]];28 }29 30 long long ans = 0;31 for(int i=0;i<n;i++) {32 if(vis[i])33 continue;34 long long sum = 0;35 36 for(int j=i;!vis[j];j=a[j]) {37 sum +=(abs(j-a[j]));38 vis[j] = 1;39 }40 ans +=(sum)/2;41 }42 43 printf("%lld\n",ans);44 45 return 0;46 }
51nod 1574 排列转换
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。