↓問題のページ↓
AtCoder Beginner Contest 331 C - Sum of Numbers Greater Than Me
ぱっと見ですぐには解法を思い浮かべられなかったので体感C問題にしてはやや難しい方かなと思ったが、AtCoder Problemsの統計を見ると灰色なのでさっさと解けなければならない問題だった。何とか本番中にACを獲得できて喜ばしいことこの上ない。
解法：
1)入力される数列\(A\)と全く同じ項を持つ数列\(B\)を用意する。
↓
2)数列\(B\)を昇順に並べ替える。
↓
3)\( i = 1, \dotsc, N \)について、各項の値を以下のように定義した数列\(C\)を用意する。
\begin{equation} C_i = B_1 + \dotsb + B_i \end{equation}
↓
4)\( i = 1, \dotsc, N \)について、二分探索を用いて\( A_i < B_j \) なる最小の\(j\)を求める。そのような\(j\)が存在する場合は\( C_N - C_{j-1} \)を、存在しない場合は\(0\)を出力する。
計算量の考察：
1)で\( \mathcal{O}(N) \)の処理、2)で\( \mathcal{O}(N\log N) \)の処理、3)で\( \mathcal{O}(N) \)の処理（漸化式のように計算すれば可能）、4)では二分探索を\(N\)回実行するため\( \mathcal{O}(N\log N) \)の処理を行う。最も重い\( \mathcal{O}(N\log N) \)が全体としての計算量となり、制約で示された\(N\)でも間に合う。
