← 返回题目列表

Codeforces · 363/B

B. 栅栏

中文机器翻译题面 查看原题

波利卡普斯的家门前有一道栅栏。栅栏由n块宽度相同的木板组成,从左到右依次排列。第 i 块木板的高度为 hi 米,不同的木板可以具有不同的高度。

n = 7 且 h = [1, 2, 6, 1, 1, 7, 1] 的栅栏

Polycarpus 买了一架豪华钢琴,正在考虑如何把它搬进屋里。为了执行他的计划,他需要从栅栏上连续取出 k 块木板。较高的木板更难从栅栏上撕下来,因此 Polycarpus 想要找到这样 k 个连续的木板,使得它们的高度总和尽可能小。

编写程序,查找总高度最小的 k 个连续木板的索引。注意,栅栏不是在波利卡普斯的家周围,而是在家的前面(换句话说,栅栏不是循环的)。

输入

输入的第一行包含整数 n 和 k (1 ≤ n ≤ 1.5·105, 1 ≤ k ≤ n) — 栅栏中的木板数量和钢琴孔的宽度。第二行包含整数序列 h1, h2, ..., hn (1 ≤ hi ≤ 100),其中 hi 是栅栏第 i 块木板的高度。

输出

打印这样的整数 j ,使得木板 j、j + 1、...、j + k - 1 的高度之和尽可能最小。如果有多个这样的 j,则打印其中任何一个。

示例

输入 #1

7 3
1 2 6 1 1 7 1

输出 #1

3

注意

在示例中,您的任务是找到高度总和最小的三个连续木板。在给定的情况下,索引为 3、4 和 5 的三块木板具有所需的属性,它们的总高度为 8。