[AtCoder] ABC 173 D – Chat in a Circle

問題

方針

証明をしないとダメだと思いますが、貪欲法で考えます。\( 2 \) 人目以降の到着で心地よさが増えることと、心地よさの増分は一人分だけであることを考慮して、その時々で心地よさを最大化します。まず初めに、配列を降順に並び替え、\( A_0 \) が到着したとします。次に、\( A_1, A_2, … \) と順番に到着すると、心地よさの和は、

\[A_0 + A_1 + A_1 + A_2 + A_2 + A_3 + A_3 + \cdots\]

となります。

コード