UVA - 10570 Meeting with Aliens

UVA - 10570 Meeting with Aliens

題目大意：N個外星人圍成一桌坐下，有序的排列指N在N-1與N+1中間，現在給出一個序列，問至少交換幾次可以得到有序的序列。

解題思路：不管結果如何，我們可以假設最終的序列是以某個外星人為起點的有序序列，既然如此，我們可以構造另一個序列，把原來的外星人長度增加一倍，這樣一來，原序列一定是這個構造序列的子序列。然後通過枚舉，可以把最小交換次數求出來。繼而解決下一個問題：如何求最小的交換次數？我們可以把1與1號位置的交換，2與2號位置的交換，這樣求出的序列即是最小的，這個結論可以記住。然後再反過來求一遍即可，因為題目要求是正、反序列。
 

#include 
#include 
using namespace std;

int cal(int A[], int N) {
    int cnt = 0, vis[505] = {0};
    for (int i = 1; i <= N; i++)
        if(!vis[i]) {
            cnt++;
            for (int j = i; !vis[j]; j = A[j])
                vis[j] = 1;
        }
    return N - cnt;
} 

int main() {
    int N, A[1010], B[1010];
    while (scanf("%d", &N), N) {
        for (int i = 1; i <= N; i++) {
            scanf("%d", &A[i]);
            B[N - i + 1] = B[2 * N - i + 1] = A[i + N] = A[i];
        }

        int ans = 1 << 30;
        for (int i = 0; i < N; i++)
            ans = min(ans, cal(A + i, N));

        for (int i = 0; i < N; i++)
            ans = min(ans, cal(B + i, N));

        printf("%d\n", ans);
    }

    return 0;
}