A83453.大树下的阴凉处
普及-
官方
通过率:0%
时间限制:1.00s
内存限制:128MB
题目描述
在一条直线道路旁种着一排树,第 i 棵树在正午时能提供的阴凉“强度”为 ai。你想找一个长度恰好为 k 的连续路段(也就是一段连续的树),让这段路上总体的“阴凉”最少,这样便于拍照不被树影影响。
给定 n 和数组 a1,a2,…,an,请你找出和最小的长度为 k 的连续子段的起始位置(下标从 1 开始)。
若有多个子段的和同为最小,请输出起始位置最小的那个。
输入格式
-
第一行包含两个整数 n 和 k。
-
第二行包含 n 个整数 a1,a2,…,an。
输出格式
输出一个整数,表示满足条件的长度为 k 的连续子段的起始下标(1 开始)。
输入输出样例
输入#1
7 3 2 1 3 1 1 2 3
输出#1
4
说明/提示
-
1≤n≤2×105
-
1≤k≤n
-
−109≤ai≤109
所有长度为 3 的连续子段及其元素和:
- 位置 1 开始:2+1+3=6
- 位置 2 开始:1+3+1=5
- 位置 3 开始:3+1+1=5
- 位置 4 开始:1+1+2=4
- 位置 5 开始:1+2+3=6
最小的和是 4,出现在起始位置 4,因此输出 4。