首页 > 代码库 > CodeForces Good Bye 2014 B. New Year Permutation
CodeForces Good Bye 2014 B. New Year Permutation
可能是因为这次没有分Div.1和Div.2，所以感觉题的难度比较大。
题意：
给出一个1~n的排列和一个邻接矩阵A，Aij = 1表示可以交换排列的第i项和第j项，问经过若干次交换后，求能够得到最小字典序的排列。
分析：
如果a和b可交换，b和c可交换，则a和c也可以交换位置。如果把这n个位置看做顶点，两个可交换的位置连一条边，则图中在同一连通分量的顶点都是可以交换元素的。所以用并查集做就很方便了。
要想得到字典序最小的排列，直接贪心就可以了。从第一个数开始，首先试试1能不能交换到第一个位置去，否则尝试2，一直到能交换或者没有比开头的数更小的数位置。然后继续尝试第二个数。代码中有个used标记数组，标记这个数是否在前面用过。
1 #include <cstdio> 2 #include <algorithm> 3 4 const int maxn = 300 + 5; 5 char G[maxn][maxn]; 6 int p[maxn], a[maxn], pos[maxn];//pos记录每个数的位置 7 bool used[maxn];//标记每个数是否用过 8 9 int GetParent(int x)10 {11 return (p[x] == x ? x : p[x] = GetParent(p[x]));12 }13 14 void Union(int x, int y)15 {16 int px = GetParent(x), py = GetParent(y);17 if(px != py)18 p[px] = py;19 }20 21 int main()22 {23 //freopen("in.txt", "r", stdin);24 int n;25 scanf("%d", &n);26 for(int i = 1; i <= n; ++i) p[i] = i;27 for(int i = 1; i <= n; ++i) scanf("%d", &a[i]);28 for(int i = 1; i <= n; ++i) scanf("%s", G[i] + 1);29 30 for(int i = 1; i <= n; ++i) pos[a[i]] = i;31 32 for(int i = 1; i <= n; ++i)33 for(int j = 1; j <= n; ++j)34 if(G[i][j] == ‘1‘) Union(i, j);35 36 for(int i = 1; i < n; ++i)37 {38 used[a[i]] = true;39 for(int j = 1; j < a[i]; ++j)40 {41 if(used[j]) continue;42 if(GetParent(i) == GetParent(pos[j]))43 {44 used[a[i]] = false;45 used[j] = true;46 int q = pos[j];47 std::swap(a[i], a[q]); //交换两元素48 std::swap(pos[a[i]], pos[a[q]]); //同时交换每个数的位置49 break;50 }51 }52 }53 54 for(int i = 1; i < n; ++i) printf("%d ", a[i]);55 printf("%d\n", a[n]);56 57 return 0;58 }
CodeForces Good Bye 2014 B. New Year Permutation
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。