UVA - 10570 Meeting with Aliens 暴力

发布时间：2020-12-13 20:43:31 所属栏目：PHP教程来源：网络整理

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

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

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!