Chef and Hamming Distance of arrays [CodeChef December Challenge 2017 D]

https://www.codechef.com/DEC17/problems/CHEFHAM

N個の配列Aがある。
この配列は同じ数が3つ以上は現れない。
この配列を並び替えて配列Bを作る。
AとBのハミング距離が最大となる配列Bの答えよ。
ハミング距離:= A[i] != B[i]となるiの個数

解法

場合分けしながら考えていく。
N=1の時は並び替えようが無いので、そのまま。
N=2の時はA[0]=A[1]なら並び替えようがないので、そのまま。A[0]!=A[1]であれば、逆転すればハミング距離2で最大。どちらの場合もとりあえず逆転させればいい。
3≦Nの時は最善手法があるので、それを行う。
例えばA={1,1,2,2,3,3}であるとする。この場合に2の所に1を3の所に2を1の所に3を入れればハミング距離を最大化できる。
直感的には今の数は次に大きい数がある部分へ移してやればハミング距離が最大化できそうなことが分かる。
下のプログラムでは数を昇順でソートしたときに2つ大きい数がある場所に書き込むようにしている。

あとは、上の場合分けで構築したBと配列Aで実際にハミング距離を求めて答える。

int N, A[101010], B[101010];
//---------------------------------------------------------------------------------------------------
void solve() {
    cin >> N;
    rep(i, 0, N) cin >> A[i];

    if (N == 1) B[0] = A[0];
    else if (N == 2) {
        B[0] = A[1];
        B[1] = A[0];
    } else {
        vector<pair<int, int>> v;
        rep(i, 0, N) v.push_back({ A[i], i });
        sort(v.begin(), v.end());

        rep(i, 0, N) {
            auto p = v[i];
            int j = (i + 2) % N;
            auto q = v[j];
            B[q.second] = p.first;
        }
    }

    int ans = 0;
    rep(i, 0, N) if (A[i] != B[i]) ans++;
    printf("%d\n", ans);
    rep(i, 0, N) {
        if (i) printf(" ");
        printf("%d", B[i]);
    } printf("\n");
}
//---------------------------------------------------------------------------------------------------
void _main() {
    int T; cin >> T;
    rep(t, 0, T) solve();
}