Problem4439--排队

4439: 排队

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 256 MiB

Description

洛洛在外出旅游的时候发现社会上文明的现象越来越多,人们在买票的时候都会自发地排队等候。
遗憾的是排队的人身高参差不齐,有时候前后两人之间的身高相差太大,缺乏一些美感。
如果把前后两人的身高差(差值为正数)表示为两者前后相邻时产生的违和度,一段连续的人群因为前后两人身高不同而产生的违和度之和就可以被称为违和值。
洛洛希望知道在队伍哪一段,且该段队伍由连续的 $m$ 个人组成,其违和值最小。

Input

第一行输入两个正整数 $n,\ m$,$n$ 表示队伍的总人数,$m$ 表示某一段的人数。
第二行输入 $n$ 个整数,表示队伍中 $n$ 个人的身高,单位厘米。

Output

输出包含一个整数,即最小的违和值。

Constraints

对于 $50\%$ 的数据保证 $2 ≤ n ≤ 10$;
对于 $80\%$ 的数据保证 $2 ≤ n ≤ 1000$;
对于 $100\%$ 的数据保证 $2 ≤ n ≤ 100000,\ 1 ≤ m < n$。
每个人的身高不超过 $300$ 厘米。

Sample 1 Input

4 3
10 7 5 4

Sample 1 Output

3
$m=3$,要选取 $3$ 个连续的人有两种选法:
$10\ 7\ 5$:违和度之和 $3+2=5$。
$7\ 5\ 4$:违和度之和 $2+1=3$。
所以答案是 $3$。

HINT

问题来源:2019年绍兴市第十七届少儿信息学竞赛复赛

REF Vedio

Source/Category