分数: 333 分
问题陈述
高桥经营着一个果园。果园有 N 果树排成一排,编号 1, 2, \ldots, N 从左到右。
的 i第棵树熊 A_i 水果。
由于今年劳动力短缺,高桥无法砍伐所有树木,因此他决定精确选择 K 连续树木收获。具体来说,他选择一个整数 l (1 \leq l \leq N - K + 1)并从 K 树木已编号 l 通过 l + K - 1。他必须从每一个地方收获所有的果实。 K 选择了树(他不能部分收获一棵树),并且他不会从他没有选择的树上收获任何果实。
高桥希望尽量减少工作量,因此他希望尽量减少收获的水果总数。
找出当 K 连续的树被最优选择。
约束
- 1 \leq K \leq N \leq 2 \times 10^5
- 1 \leq A_i \leq 10^9
- 所有输入均为整数。
输入
N K A_1 A_2 \ldots A_N
第一行包含整数 N 表示果园中树木的数量和整数 K 代表要采伐的连续树木的数量,以空格分隔。
第二行包含整数 A_1, A_2, \ldots, A_N 代表每棵树上的水果数量,以空格分隔。
输出
在一行中打印出当 K 连续的树被最优选择。
示例输入 1
5 3 4 2 1 3 5
示例输出 1
6
示例输入 2
8 4 10 5 8 3 2 7 4 6
示例输出 2
16
示例输入 3
10 5 100 200 50 80 120 30 60 90 150 70
示例输出 3
340