Chat in a Circle [AtCoder Beginner Contest 173 D]

https://atcoder.jp/contests/abc173/tasks/abc173_d

解説

https://atcoder.jp/contests/abc173/submissions/15023990

難しい問題。
「N人の到着順番や割り込む位置を適切に決める」とあるが、決めるべきことが多すぎる。
こういう時は、固定できそうな所を探すといい。
以下、未証明。

一部固定する

まず、到着順番は降順で入れていくのがいい。
（これはある降順でない順番があったときに、
それを大小関係を維持しつつ降順に言い換えたときに状況が同じか改善されるかのどちらかであるため。）
理由についてはあまり気にしなくてもいいかも。
この程度の仮定がないと解くのは難しい。

貪欲法

次に割り込む位置であるが、複雑なルールは作りたくないので、実験でとりあえず貪欲にやってみる。
すると、昇順でA,B,C,D,E,...となった場合に、
0+A+B+B+C+C+D+D+E+E+...
のようになっていることが実験で分かる。
完全二分木っぽく自分は考えた。
あとは、これを実装するだけ。

int N, A[201010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) cin >> A[i];
    sort(A, A + N, greater<int>());

    ll ans = A[0];
    rep(i, 0, N - 2) ans += 1LL * A[i / 2 + 1];
    cout << ans << endl;
}