【链接】

【题意】

在这里输入题意

【题解】

枚举1的位置在i

往右摆成一排。

a[i+1]..a[n]..a[1]..a[i-1]变为有序的

->寻找循环节,每个循环节的长度-1是必要的步骤数

->获取必要的步骤数,取最小值。

->O(n^2)

往左排成一排

->同样的方法处理就好

【代码】

#include 
    
     using namespace std;const int N = 5e2;int a[N+10],n,cnt;bool flag[N+10];vector 
     
       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;}