← 返回题目列表

AtCoder · awc0008_c

C. 传感器数据异常检测

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

分数: 333 分

问题陈述

Takahashi 正在为一家工厂开发质量控制系统。该系统需要监控从安装在生产线上的传感器收集的数据并检测异常时期。

传感器执行 N 测量,并按从开始的顺序记录数据 1-st 到 N第一次测量。获得的值在 i第次测量(1 \leq i \leq N) 是一个整数 A_i 称为“质量指数”。质量指数可为正值, 0,或负数。

作为质量控制标准,如果一个窗口上的质量指数之和恰好为 K 连续测量是 0 或更少,该间隔被分类为“异常期间”。更准确地说,对于每个起始位置 j (1 \leq j \leq N - K + 1),如果

$A_j + A_{j+1} + \cdots + A_{j+K-1} \leq 0$

成立,则从位置开始的间隔 j (来自 j-第 (j+K-1)第次测量)是异常周期。

查找归类为异常时段的区间数,即起始位置数 j 满足上述条件。不同起始位置对应的区间即使相互重叠也单独计数。

约束

  • 1 \leq K \leq N \leq 2 \times 10^5
  • -10^9 \leq A_i \leq 10^9
  • 所有输入值均为整数。

输入

N K
A_1 A_2 \ldots A_N
  • 第一行包含一个整数 N 表示测量次数和一个整数 K 表示用于异常检测的间隔长度,以空格分隔。
  • 第二行包含整数 A_1, A_2, \ldots, A_N 代表每次测量的质量指数,以空格分隔。

输出

在一行中打印被分类为异常周期的间隔数。


示例输入 1

5 3
2 -1 -3 4 1

示例输出 1

2

示例输入 2

8 4
1 -2 3 -4 2 -1 -3 5

示例输出 2

4

示例输入 3

15 5
100 -50 -30 -25 10 -200 150 80 -100 -60 20 -10 5 -15 30

示例输出 3

7