https://atcoder.jp/contests/arc086/tasks/arc086_b
- 構築する
- 最短である必要はない
- 2N回も必要なケースあるのかな？
- 6,5,4,3,2,1を全部+1だけで条件を満たそうとすると超えるが、そんなことはしない
- 2番目に対して1番目以上になる最小の数を足し…とやっていってOKか？
- O(NlogN)
- Nが50とかなり小さい
- もっとオーダーの大きなアルゴリズム？
- 公式解説
- 元の数ではなく更新した数が使われるのが厄介だと思ったが、むしろそれを活用する
- 符号が揃っている場合は累積和でできる
- 気づかなかったなぁ
- 正の数の累積和は単調増加
- 符号を揃えるのがN以下でできる