問題一覧 > 通常問題

No.738 平らな農地

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 77
作問者 : しらっ亭しらっ亭 / テスター : はむこはむこ
3 ProblemId : 1732 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2018-09-28 15:08:39

問題文

$N$ 個の整数からなる配列 $A$ が与えられます。

$A$ の任意の要素を任意の整数に変更する操作を何度でも行うことができます。操作には $1$ 回ごとにコストが必要で、値を $a$ から $b$ に変更するには、コストが $|a-b|$ 必要です。

操作によって $A$ の中に「値が同じである $K$ 個以上連続した要素」を $1$ つ以上作り出すのに必要なコストの最小値を求めて下さい。

問題文(ストーリー付き)

雪男君は東西に続く $N$ ブロックの土地を持っています。この土地を整地して畑を作り農業をしようと考えています。

雪男君はまず、各ブロックの標高を計測しました。西から $i$ 番目のブロックの標高は $A_i$ メートルでした。($A_i$ は正の整数)

畑を作るには、標高が同じである $K$ ブロック以上連続した土地が必要です。畑が平らでなかったり離れ離れだと、効率が悪いからです。

あなたは、任意の $1$ ブロックの標高を任意の整数に変更する整地を何度でも行うことができます。整地には $1$ 回ごとにコストが必要で、標高を $a$ メートルから $b$ メートルに変更するには、コストが $|a-b|$ 必要です。

整地によって「標高が同じである $K$ ブロック以上連続した土地」を作り出すのに必要なコストの最小値を求めて下さい。

入力

$N$ $K$
$A_1$ $A_2$ $A_3$ $\dots$ $A_N$

$1 \le K \le N \le 10^5$
$1 \le A_i \le 10^9$
入力は全て整数

出力

答えを1行で出力してください。
最後に改行してください。

サンプル

サンプル1
入力
9 2
1 4 1 4 2 1 3 5 6
出力
1

例えば、$A_5$ を $1$ 減少させることで $A_5, A_6$ の連続する $2$ ブロックの標高を同一にできます。
他にも、$A_6$ を $1$ 増加させる、$A_8$ を $1$ 増加させる、$A_9$ を $1$ 減少させる、などの方法でも最小コスト $1$ を達成できます。

サンプル2
入力
10 5
3 1 4 1 5 9 2 5 6 3
出力
7

コスト $7$ で ${A_1, A_2, A_3, A_4, A_5}$ を $3$ に揃えることができ、これが最小コストです。

サンプル3
入力
5 5
1 2 3 4 5
出力
6

$K=N$ の場合もあります。

サンプル4
入力
7 3
1 2 3 3 3 4 5
出力
0

最初から揃っている場合もあります。

サンプル5
入力
5 3
1 1 2 1 1
出力
1

長さが丁度 $K$ である必要はありません。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。