ARC128 C - Max Dot (600)
$ x_iの値を切り替えるところは後ろから見て$ A_iが昇順になっている部分列の最後尾が良い
コンテスト中の考察1
$ A_iが大きい順に見ていく
そこに可能な限り最大の値を入れていく
$ \max \left(m,\frac{残量}{区間の長さ}\right)
他の区間の方が平均値が高くなる場合があるので駄目
コンテスト中の考察2
$ A_iが大きい順に見ていく
前回見た位置までの平均の値を区間の値として追加
平均の降順にソート
平均が大きい順に見ていく
そこに可能な限り最大の値を入れていく
$ \max \left(m,\frac{残量}{区間の長さ}\right)
他の区間の方が平均値が高くなる場合があるので駄目
コンテスト中の考察3
後ろから見て最後尾から現在までの平均が高い順に見ていく
そこに可能な限り最大の値を入れていく
$ \max \left(m,\frac{残量}{区間の長さ}\right)
解説の解法
考察3の場合、$ mが使う量として選ばれると後ろで使えなかった値が前側に繰り越されるので平均を計算し直す必要がある
最大で$ N回計算し直すので全体で$ \mathcal{O}(N^2)