Codeforces Round #353 (Div. 2) C. Money Transfers
http://codeforces.com/contest/675/problem/C
問題
数列 an が与えられる。i 番目にある値を i-1,i+1 のどちらかに流すという操作ができる。
すべての要素を 0 にするのに必要な最小の操作回数を求めよ。
- 2≦n≦105
- 1≦a[i]≦109
解法
右だけに移動させるように限定しても、最小ステップ数は変わらないはず。
となるとスタート地点を一つ決めて、0になるまで右に流し続けるという貪欲をやれば答えが求まる。
簡単な例をひとつ示した。矢印の終着点の要素は移動させなくてもいいので、n-(矢印の本数)が必要な移動回数になる。
累積和の世界で見ると、矢印の終着点はからなず同じ値になる。なぜなら、S[i+n]=S[i] なら S[i..i+n-1]=0 になるからだ。
つまり累積和の中で一番多く現れる値の個数を n から引いてあげれば、それが答えになる。
スタート地点の選び方は n 通りあるので、愚直にやると O(n2)。しかし、この方法であれば map を用いて O(n log n) で解ける。
Codeforces Round #353 (Div. 2) C. Money Transfers
本番は i 番目からどこまで足せば 0 になるかを前計算しておいて、流す作業を高速化して通した。累積和の頻度を見るの頭いいな。