uva10570 Meeting with Aliens

先证明把每次i放到i位置最后次数最少：感觉，可以，用归纳法？

//在序列后再加一个相同的序列，就可以模拟用各个数字开头的情况了
每个位置不对的只需要换一次
54123 ，5固定->41235变成12345

任何一个数固定不变，都相当于从这种情况对应的1所在的位置开始排一遍12345.（例如54123 ，5固定->41235变成12345）所以只需要每个位置开始都判断变成12345所需步数即可

把输入倒过来看，变成12345就相当于正着变成54321 （这个对称很巧妙啊），可以模块化

#include <cstdio>

#include <algorithm>

using namespace std;

int cal(int A[], int N) {    //54123—>12345可以看做12354->12345所以每个位置开始都判断变成12345所需步数即可

    int cnt = , vis[] = {};

    for (int i = ; i <= N; i++)  //cnt统计不用换位的个数；不用换位的A[j]就等于j,进入下一个数了

        if(!vis[i]) {            //某个数还没到正确位置

            cnt++;

            for (int j = i; !vis[j]; j = A[j])   //这个循环中一直换位直到不用换

                vis[j] = ;

        }

    return N - cnt;

}

int main() {

    int N, A[], B[];

    while (scanf("%d", &N), N) {

        for (int i = ; i <= N; i++) {

            scanf("%d", &A[i]);

            B[N - i + ] = B[ * N - i + ] = A[i + N] = A[i];

        }

        int ans =  << ;

        for (int i = ; i < N; i++)

            ans = min(ans, cal(A + i, N));

        for (int i = ; i < N; i++)

            ans = min(ans, cal(B + i, N));

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

    }

    return ;

}

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int N = ;

int p[N],k[N],w[N];

int f[N],n;

int solve(int s, int d) {

    int cnt = ;

    for(int i = ; i <= n; i++) {

        if(k[i] != s) {

            cnt++;

            k[w[s]] = k[i];

            w[k[i]] = w[s];

            k[i] = s;

            w[s] = i;

        }

        s += d;

        if(s > n)

            s = ;

        if(s <= )

            s = n;

    }

    return cnt;

}

int main() {

    while(scanf("%d",&n) && n) {

        for(int i = ; i <= n; i++) {

            scanf("%d",&p[i]);

            f[p[i]] = i;

        }

        int Min = 0x3f3f3f3f;

        for(int i = ; i <= n; i++) {

            memcpy(k, p, sizeof(p));

            memcpy(w, f, sizeof(f));

            Min = min(Min, solve(i,-));

            memcpy(k, p, sizeof(p));

            memcpy(w, f, sizeof(f));

            Min = min(Min, solve(i,));

        }

        printf("%d\n",Min);

    }

}