天佑家准备装修他的豪宅啦,但是他家的房子前有一道栅栏,栅栏由 n 块宽度相同的木板组成,从左到右依次排列,第 i 块木板的高度为 hi 米。
如上图,n=7,高度分别为1, 2, 6, 1, 1, 7, 1
天佑知道他家购买的家具的最大宽度为 k ,为了实现他家的装修计划,他家需要从栅栏上连续拆除 k 块木板。显然,越高的木板越难拆除,请你帮助天佑找出一组长度为 k 的木板序列,使这个序列的高度之和尽量小。
天佑家准备装修他的豪宅啦,但是他家的房子前有一道栅栏,栅栏由 n 块宽度相同的木板组成,从左到右依次排列,第 i 块木板的高度为 hi 米。
如上图,n=7,高度分别为1, 2, 6, 1, 1, 7, 1
天佑知道他家购买的家具的最大宽度为 k ,为了实现他家的装修计划,他家需要从栅栏上连续拆除 k 块木板。显然,越高的木板越难拆除,请你帮助天佑找出一组长度为 k 的木板序列,使这个序列的高度之和尽量小。
第一行包括两个整数 n 和 k(1<=n<=1.5*1e5,1<=k<=n)分别代表栅栏长度与家具的最大宽度。第二行包括 n 个整数 h1 ,h2 ,…,hn(1<=hi<=100)分别代表第 i 块木板的高度。
一个整数 j ,使第j块木板到第j+k-1块木板的高度的和尽量小,如果有多个这样的 j ,输出最小的那个。
7 3 1 2 6 1 1 7 1
3
栅栏为一条直线,也就是说,不存在环。
针对样例,应该选从位置3开始的连续3块木板,加起来的高度为8