問題
サイズNの数列が与えられる。ある要素に対して1を足したり引いたりする操作のコストを1とする。k個の連続した数字を得るための最小のコストを求めよ。
解法
与えられた数列を昇順にソートする。
数列のある要素を選択し、その要素を中心にk個の連続した要素を最小コストで作成していく。隣接している要素ごとに調べていけば、最小のコストで構築できる。これを全部の要素に対して行う。
計算量
ソート:
全体:
サイズNの数列が与えられる。ある要素に対して1を足したり引いたりする操作のコストを1とする。k個の連続した数字を得るための最小のコストを求めよ。
与えられた数列を昇順にソートする。
数列のある要素を選択し、その要素を中心にk個の連続した要素を最小コストで作成していく。隣接している要素ごとに調べていけば、最小のコストで構築できる。これを全部の要素に対して行う。
ソート:
全体: