首页 > 代码库 > 51nod 1574 排列转换

51nod 1574 排列转换

2024-09-26 07:11:39   285人阅读

技术分享

 

 

分析：

大佬们也有搞错的时候，说把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 }
View Code

 

51nod 1574 排列转换


联系
我们