題目大意：有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;
}
程序員人生，我編程，我富裕，記住wfuyu網，php教程，php學習，php手冊，CMS模版制作
聲明：本站大部分內容是作者原創，少部分收集于互聯網供大家一起學習，原版權很多不明，如有侵權請聯系本站，謝謝！
粵ICP備14040726號-1?? 2015-2020 程序員人生 版權所有
