【习题 8-13 UVA - 10570】Meeting with Aliens

【链接】 我是链接,点我呀:)

【题意】

在这里输入题意

【题解】

枚举1的位置在i
往右摆成一排。
a[i+1]..a[n]..a[1]..a[i-1]变为有序的
->寻找循环节,每个循环节的长度-1是必要的步骤数
->获取必要的步骤数,取最小值。
->O(n^2)
往左排成一排
->同样的方法处理就好

【代码】

#include <bits/stdc++.h>

using namespace std;

const int N = 5e2;

int a[N+10],n,cnt;

bool flag[N+10];

vector <int> v;

int get_step(){

    memset(flag,0,sizeof flag);

    int now = 0;

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

        if (!flag[i]){

            int cc = 0,kk = i;

            while (!flag[kk]){

                flag[kk] = true;

                cc++;

                kk = v[kk];

            }

            now+=cc-1;

        }

    return now;

}

int main(){

	#ifdef LOCAL_DEFINE

	    freopen("rush_in.txt", "r", stdin);

	#endif

	ios::sync_with_stdio(0),cin.tie(0);

    while (cin >>n && n){

        for (int i = 1;i <= n;i++) cin >> a[i];

        int j = 1;

        for (int i = 2;i <= n;i++) if (a[i]==1) j = i;

        int ans = -1;

        v.resize(n+1);

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

            cnt = 0;

            if (i!=j){

                swap(a[i],a[j]);

                cnt++;

            }

            //向右

            for (int k = 1,l = i;k <= n;k++,l++){

                if (l>n) l = 1;

                v[k] = a[l];

            }

            int temp1 = get_step();

            //向左

            for (int k = 1,l = i;k <= n;k++,l--){

                if (l<=0) l = n;

                v[k] = a[l];

            }

            int temp2 = get_step();

            if (ans==-1){

                ans = cnt+min(temp1,temp2);

            }else{

                ans = min(ans,cnt+min(temp1,temp2));

            }

            if (i!=j) swap(a[i],a[j]);

        }

        cout << ans << endl;

    }

	return 0;

}