问题 BS: 排队

内存限制:128 MB 时间限制:1 S 标准输入输出
题目类型:传统 评测方式:文本比较 上传者:
提交:1592 通过:606

题目描述

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

输入格式

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



输入:
8 3
157 72 68 232 251 38 204 123



输出:
89


输出格式

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

输入样例 复制

4 3
10 7 5 4

输出样例 复制

3

数据范围与提示

m=3,要选取 3 个连续的人有两种选法:
10 7 5: 违和度之和=3+2=5
7 5 4
: 违和度之和=2+1=3
所以答案是 3
对于 50%的数据保证 2 ≤ n ≤ 10
对于
80%的数据保证 2 ≤ n ≤ 1000
对于
100%的数据保证 2 ≤ n ≤ 1000001 ≤ m < n,每个人的身高不超过 300 厘米。