A5384. 大树下的阴凉处
编程题
普及-
知识点
题目描述
在一条直线道路旁种着一排树，第 $i$ 棵树在正午时能提供的阴凉“强度”为 $a_i$。你想找一个长度恰好为 $k$ 的连续路段（也就是一段连续的树），让这段路上总体的“阴凉”最少，这样便于拍照不被树影影响。
给定 $n$ 和数组 $a_1,a_2,\dots,a_n$，请你找出和最小的长度为 $k$ 的连续子段的起始位置（下标从 1 开始）。
若有多个子段的和同为最小，请输出起始位置最小的那个。
给定 $n$ 和数组 $a_1,a_2,\dots,a_n$，请你找出和最小的长度为 $k$ 的连续子段的起始位置（下标从 1 开始）。
若有多个子段的和同为最小，请输出起始位置最小的那个。
输入格式
- 第一行包含两个整数 $n$ 和 $k$。
- 第二行包含 $n$ 个整数 $a_1,a_2,\dots,a_n$。
- 第二行包含 $n$ 个整数 $a_1,a_2,\dots,a_n$。
输出格式
输出一个整数，表示满足条件的长度为 $k$ 的连续子段的起始下标（1 开始）。
输入输出样例
输入 #1
7 3 2 1 3 1 1 2 3
输出 #1
4
说明/提示
- $1 \le n \le 2\times 10^5$
- $1 \le k \le n$
- $-10^9 \le a_i \le 10^9$
所有长度为 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。
- $1 \le k \le n$
- $-10^9 \le a_i \le 10^9$
所有长度为 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。