首页 > 代码库 > UVa10570 Meeting with Aliens (枚举)
UVa10570 Meeting with Aliens (枚举)
链接：http://vjudge.net/problem/UVA-10570
分析：枚举环状排列的循环表示的第一个数字，每次将一个数字放到其正确的位置上，顺时针和逆时针方向各统计一次需要的交换次数并取两者最小值。
1 #include <cstdio> 2 #include <algorithm> 3 #include <cstring> 4 using namespace std; 5 6 const int maxn = 500 + 5; 7 8 int n, data[maxn], idex[maxn], a[maxn], aIdex[maxn]; 9 10 int main() {11 while (scanf("%d", &n) == 1 && n) {12 for (int i = 0; i < n; i++) {13 scanf("%d", &data[i]); --data[i];14 idex[data[i]] = i;15 }16 int ans = maxn;17 for (int start = 0; start < n; start++) {18 memcpy(a, data, sizeof(data));19 memcpy(aIdex, idex, sizeof(idex));20 int cnt1 = 0;21 for (int i = 0; i < n; i++)22 if (a[i] != (start + i) % n) {23 swap(a[i], a[aIdex[(start + i) % n]]);24 swap(aIdex[a[aIdex[(start + i) % n]]], aIdex[(start + i) % n]);25 cnt1++;26 }27 memcpy(a, data, sizeof(data));28 memcpy(aIdex, idex, sizeof(idex));29 int cnt2 = 0;30 for (int i = 0; i < n; i++)31 if (a[i] != (start - i + n) % n) {32 swap(a[i], a[aIdex[(start - i + n) % n]]);33 swap(aIdex[a[aIdex[(start - i + n) % n]]], aIdex[(start - i + n) % n]);34 cnt2++;35 }36 ans = min(ans, min(cnt1, cnt2));37 }38 printf("%d\n", ans);39 }40 return 0;41 }
UVa10570 Meeting with Aliens (枚举)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。