UnKoder #05 C Chairs in Circle

2015/05/20 (Wed) hackerrank UnKoder 転置数

問題

問題文

方針

両端が繋がっていなければただの転置数を求めればよい．

ある一人の生徒に注目すると，置換の回数は $N$ 以下なので最初からの延べの移動距離は最大でも $1$ 周である．また，$1$ 周するような生徒がいない場合は，全く移動しない隣り合う $2$ 人が必ず $1$ 組以上存在する．

なので，その場所を決めた後，$2$ 人を置換せずにそこで輪を切って普通の列にして転置数を求める場合と， 置換してから切る場合を全て試せばよい．

実装

int solve(vi a, vi b){
    int N = a.size();
    vi ord(N);
    rep(i,N) ord[a[i]] = i;
    int ans = 0;
    rep(i,N)rep(j,i){
        if(ord[b[j]] > ord[b[i]]) ans++;
    }
    return ans;
}

signed main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    int N;
    cin >> N;

    vi a(N), b(N);
    rep(i,N){
        cin >> a[i];
        a[i]--;
    }
    rep(i,N){
        cin >> b[i];
        b[i]--;
    }
    int ans = INT_MAX;

    rep(i,N){
        ans = min(ans,solve(a,b));
        rotate(a.begin(),a.begin()+1,a.end());
        rotate(b.begin(),b.begin()+1,b.end());
    }
    rep(i,N){
        swap(a[0],a[N-1]);
        ans = min(ans,solve(a,b)+1);
        swap(a[0],a[N-1]);
        rotate(a.begin(),a.begin()+1,a.end());
        rotate(b.begin(),b.begin()+1,b.end());
    }
    cout << ans << endl;
}