きままにものづくり

日々の気付いたことなんかを書いてます。

SRM646Div1Easy

問題

サイズNの数列が与えられる。ある要素に対して1を足したり引いたりする操作のコストを1とする。k個の連続した数字を得るための最小のコストを求めよ。

解法

与えられた数列を昇順にソートする。
数列のある要素を選択し、その要素を中心にk個の連続した要素を最小コストで作成していく。隣接している要素ごとに調べていけば、最小のコストで構築できる。これを全部の要素に対して行う。

計算量

ソート: O(N log N)
全体: O(N^2 log N)

コード