https://ac.nowcoder.com/acm/contest/5773/E
求使序列有序的最小交换次数。
找循环节的个数,最小交换次数等于元素个数减掉循环节的个数。
关于算法这里有个比较好的分析https://blog.csdn.net/lfb637/article/details/86653121?utm_medium=distribute.pc_relevant.none-task-blog-baidujs-3
代码如下,算是模板吧
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5;
int a[maxn],v[maxn];
int vis[maxn];
map<int,int>m;
int main()
{
int n;cin>>n;
for(int i=0;i<n;i++)scanf("%d",&a[i]),v[i]=a[i];
sort(v,v+n);
for(int i=0;i<n;i++){
m[v[i]]=i;
}
int loop=0;
for(int i=0;i<n;i++){
if(!vis[i]){
int j=i;
while(!vis[j]){
vis[j]=1;
j=m[a[j]];
}
loop++;
}
}
cout<<n-loop<<endl;
return 0;
}
原文链接: https://www.cnblogs.com/mohari/p/12961057.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/197857
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!