问题 5160 --天佑家装修豪宅

5160: 天佑家装修豪宅★★

时间限制: 1 Sec  内存限制: 128 MB
提交: 234  解决: 85
[提交][状态][命题人:]

题目描述

天佑家准备装修他的豪宅啦,但是他家的房子前有一道栅栏,栅栏由 n 块宽度相同的木板组成,从左到右依次排列,第 i 块木板的高度为 hi 米。

如上图,n=7,高度分别为1, 2, 6, 1, 1, 7, 1

天佑知道他家购买的家具的最大宽度为 k ,为了实现他家的装修计划,他家需要从栅栏上连续拆除 k 块木板。显然,越高的木板越难拆除,请你帮助天佑找出一组长度为 k 的木板序列,使这个序列的高度之和尽量小。

输入

第一行包括两个整数 n k(1<=n<=1.5*1e51<=k<=n)分别代表栅栏长度与家具的最大宽度。第二行包括 n 个整数 h1 h2 hn(1<=hi<=100)分别代表第 i 块木板的高度。

输出

一个整数 j ,使第j块木板到第j+k-1块木板的高度的和尽量小,如果有多个这样的 j ,输出最小的那个。

样例输入
Copy
7 3 
1 2 6 1 1 7 1
样例输出
Copy
3

提示

栅栏为一条直线,也就是说,不存在环。

针对样例,应该选从位置3开始的连续3块木板,加起来的高度为8

来源

[提交][状态]