No.738 Flat Farmland
しらっ亭
はむこProblem Statement
You are given an array $A$ consisting of $N$ integers.
You may perform any number of times an operation that changes any element of $A$ to any integer. Each time you perform $1$ operation, a cost is incurred: changing a value from $a$ to $b$ costs $|a-b|$.
Find the minimum cost required to create, through these operations, at least $1$ occurrence in $A$ of "$K$ or more consecutive elements with the same value".
Problem Statement (with Story)
Yukio owns $N$ blocks of land extending from east to west. He plans to level this land, make a field, and take up farming.
Yukio first measured the elevation of each block. The elevation of the $i$-th block from the west was $A_i$ meters. ($A_i$ is a positive integer.)
To make a field, he needs land of $K$ or more consecutive blocks with the same elevation. This is because a field that is not flat, or that is split apart, is inefficient.
You may perform any number of times a leveling that changes the elevation of any $1$ block to any integer. Each time you perform $1$ leveling, a cost is incurred: changing an elevation from $a$ meters to $b$ meters costs $|a-b|$.
Find the minimum cost required to create, through leveling, "land of $K$ or more consecutive blocks with the same elevation".
Input
$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$
All input values are integers.
Output
Output the answer on 1 line.
Print a newline at the end.
Sample
Sample 1
Input
9 2 1 4 1 4 2 1 3 5 6
Output
1
For example, by decreasing $A_5$ by $1$, you can make the elevations of the $2$ consecutive blocks $A_5, A_6$ the same.
The minimum cost $1$ can also be achieved by other methods, such as increasing $A_6$ by $1$, increasing $A_8$ by $1$, or decreasing $A_9$ by $1$.
Sample 2
Input
10 5 3 1 4 1 5 9 2 5 6 3
Output
7
With cost $7$, you can make all of ${A_1, A_2, A_3, A_4, A_5}$ equal to $3$, and this is the minimum cost.
Sample 3
Input
5 5 1 2 3 4 5
Output
6
There are also cases where $K=N$.
Sample 4
Input
7 3 1 2 3 3 3 4 5
Output
0
There are also cases where the values are already equal from the start.
Sample 5
Input
5 3 1 1 2 1 1
Output
1
The length does not need to be exactly $K$.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。