Align [Tenka1 Programmer Contest C]

https://beta.atcoder.jp/contests/tenka1-2018/tasks/tenka1_2018_c

解説

https://beta.atcoder.jp/contests/tenka1-2018/submissions/3509652

構築問題。
最適な構築を考えてみる。
今回は400点問題なので、なるべく簡単に構築できるように考える。
　
絶対値というのは扱いづらいので、大きい方-小さい方として考える。
すると、ある要素は、大きい方として2回使われるか、大きい方・小さい方として1回ずつか、小さい方として2回使われるかの三択になる。
よって、大きい方なら+2, 1回ずつなら0, 小さい方なら-2となる。
端は+1か-1になる。
　
これで考えると+2になるのはなるべく大きい数にしたい。

• 2になるのはなるべく小さい数にしたい。

よって、方針として、半分にして、小さいグループと大きいグループを交互に配置していくのがいい。
Nが偶数なら、大小…大小の一択。
Nが奇数なら、大小…大小大か小大…小大小の二択の良い方が答え。
どちらも、端が+1,-1になるので、大+1の部分はなるべく小さい数を採用し、小-1はなるべく大きい値を採用する。

int N, A[101010], B[101010];
//---------------------------------------------------------------------------------------------------
ll get() {
    ll sm = 0;
    rep(i, 0, N - 1) sm += abs(B[i + 1] - B[i]);
    return sm;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) cin >> A[i];
    sort(A, A + N);
 
    ll ans = -1;
    if (N % 2 == 0) {
        rep(i, 0, N / 2) B[i * 2 + 1] = A[i];
        rep(i, 0, N / 2) B[i * 2] = A[i + N / 2];
        ans = get();
    } else {
        rep(i, 0, N / 2) B[i * 2 + 1] = A[i];
        B[N-1] = A[N/2];
        rep(i, 0, N / 2) B[i * 2] = A[i + N / 2 + 1];
        chmax(ans, get());
 
        B[0] = A[N / 2];
        rep(i, 0, N / 2) B[i * 2 + 2] = A[i];
        rep(i, 0, N / 2) B[i * 2 + 1] = A[i + N / 2 + 1];
        chmax(ans, get());
    }
    
    cout << ans << endl;
}