問題概要
$N$ 項の正整数列 $\{ A_i \}$ が与えられる．全ての（有効な） $i$ について $A_i + d_i \leq A_{ i + 1 } + d_{ i + 1 }$ にしたいとき，$\sum d$ の最小値はいくらか？
制約
- $1 \leq N \leq 2 \times 10^5$
- $1 \leq A_i \leq 10^9$
解法
手前から順に考えたときに，$d_i$ の値を不必要に大きくすると後ろで損をします．なので，各 $i$ に対して最小限の値を $d_i$ として設定していくのがよいです．
これは，$A$ の左からの累積 $\max$ をとった列を考えて，位置毎に $A_i$ の値を引いてから和をとると求まります．
コード
main = do getLine as <- readIntegers print $ sum $ zipWith (-) ( scanl1 max as ) as
