程序员人生 网站导航

UVA - 10570 Meeting with Aliens 暴力

栏目:php教程时间:2015-06-11 08:57:37

题目大意:有n个外星人要开园桌会议,外星人的编号由1到n,要求编号为i的外星人的相邻位置必须坐着编号为i⑴和编号为i+1的外星人。
现在给出n个外星人坐在圆桌上的顺序,要求你经过最少次交换(交换是两个外星人交换所座位置),使得所有外星人坐法都符合上诉规则。

解题思路:枚举每一个外星人坐的位置,假定该位置坐的必须是编号为1的外星人,然后编号从左递增或递减,最后检查该安排需要交换几次外星人
如果该外星人坐的位置是错的话,就直接把合适坐该坐位的外星人何其交换过来,这样的交换次数是最少的

#include<cstdio> #include<cstring> #define maxn 510 int pos[maxn], start[maxn], end[maxn], n; int exchange() { int cnt = 0; for(int i = 1; i <= n; i++) { if(end[i] != i) { pos[end[i]] = pos[i]; end[pos[i]] = end[i]; cnt++; } } return cnt; } void solve() { int MIN = 0x3f3f3f3f; for(int i = 1; i <= n; i++) { for(int j = 1, k = i; j <= n; j++, k++) { if(k > n) k = 1; end[j] = start[k]; pos[end[j]] = j; } int t = exchange(); MIN = (t > MIN? MIN:t); } for(int i = 1; i <= n; i++) { for(int j = 1, k = i; j <= n; j++, k--) { if(k <= 0) k = n; end[j] = start[k]; pos[end[j]] = j; } int t = exchange(); MIN = (t > MIN? MIN:t); } printf("%d ", MIN); } int main() { while(scanf("%d", &n) == 1 && n) { for(int i = 1; i <= n; i++) scanf("%d", &start[i]); solve(); } return 0; }
------分隔线----------------------------
------分隔线----------------------------

最新技术推荐