A83453.大树下的阴凉处

普及-

官方

通过率:0%

时间限制:1.00s

内存限制:128MB

题目描述

在一条直线道路旁种着一排树,第 ii 棵树在正午时能提供的阴凉“强度”为 aia_i。你想找一个长度恰好为 kk 的连续路段(也就是一段连续的树),让这段路上总体的“阴凉”最少,这样便于拍照不被树影影响。

给定 nn 和数组 a1,a2,,ana_1,a_2,\dots,a_n,请你找出和最小的长度为 kk 的连续子段的起始位置(下标从 1 开始)。
若有多个子段的和同为最小,请输出起始位置最小的那个。

输入格式

  • 第一行包含两个整数 nnkk

  • 第二行包含 nn 个整数 a1,a2,,ana_1,a_2,\dots,a_n

输出格式

输出一个整数,表示满足条件的长度为 kk 的连续子段的起始下标(1 开始)。

输入输出样例

  • 输入#1

    7 3
    2 1 3 1 1 2 3
    

    输出#1

    4
    

说明/提示

  • 1n2×1051 \le n \le 2\times 10^5

  • 1kn1 \le k \le n

  • 109ai109-10^9 \le a_i \le 10^9

所有长度为 3 的连续子段及其元素和:

  • 位置 1 开始:2+1+3=62+1+3=6
  • 位置 2 开始:1+3+1=51+3+1=5
  • 位置 3 开始:3+1+1=53+1+1=5
  • 位置 4 开始:1+1+2=41+1+2=4
  • 位置 5 开始:1+2+3=61+2+3=6

最小的和是 44,出现在起始位置 44,因此输出 4。

首页