您当前位置：首页 > php开源 > php教程 > UVA - 10570 Meeting with Aliens 暴力

UVA - 10570 Meeting with Aliens 暴力

来源：程序员人生发布时间：2015-06-11 08:57:37 阅读次数：2233次

题目大意：有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;
}

生活不易，码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
程序员人生

------分隔线----------------------------

上一篇 Linux 文本编辑工具vim

下一篇 eclipseLuna (4.4.0) 安装velocity 插件

分享到:

------分隔线----------------------------

为码而活

积分：4237

15粉丝

7关注

栏目热点