首页 > 代码库 > neu 1493 Caoshen like math（最小交换次数）
neu 1493 Caoshen like math（最小交换次数）
http://acm.neu.edu.cn/hustoj/problem.php?cid=1047&pid=4
题意：数字1到n 任意排列
求排列成有序序列最少交换次数
思路：求最小交换次数有两种
1 交换的两数必须相邻 （poj 2299）
通过归并排序求出其逆序数即为所求值
证明：可以先将最大数交换到最后，由于是相邻两个数交换，需要交换的次数为最大数后面的数的个数（可以看做是最大数的逆序数），然后，交换过后，去除最大数，再考虑当前最大数也需要其逆序数次交换。则每个数都需要交换其逆序数次操作，则总最少交换次数为序列总体的逆序数。
2 交换任意两数
也就是此题
这题有两种方法
1 第一种是每次将排完序后当前位置的值与现在当前位置的值交换 求出即为最小交换数
#include<cstdio>#include<cstring>#include<cmath>#include<algorithm>using namespace std;int a[1000000+10];int vis[1000000+10];int ans;void swap(int &a,int &b){ int temp=a; a=b; b=temp;}int main(){ int n; int i,j,k; while(scanf("%d",&n)!=EOF) { ans=0; for(i=1;i<=n;i++) { scanf("%d",&a[i]); vis[a[i]]=i; } for(i=1;i<=n;i++) { int temp=a[i]; if(a[i]!=i) { ans++; vis[temp]=vis[i]; swap(a[i],a[vis[i]]); } } printf("%d\n",ans); } return 0;}
2 求出循环节个数 ans= n-循环节个数（根据之前的坐标和排序之后的坐标，构建成一个有向图）
#include<cstdio>#include<cstring>#include<iostream>#include<algorithm>using namespace std;int num[1000000+10][2];int main(){ int n; int i,j,k; while(scanf("%d",&n)!=EOF) { int to; int ans=0;//环的个数 memset(num,0,sizeof(num)); for(i=1;i<=n;i++) { scanf("%d",&to); num[i][1]=1; num[to][0]=1; if(num[to][1]==1) ans++; } printf("%d\n",n-ans); } return 0;}
neu 1493 Caoshen like math（最小交换次数）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。