AlgoMooc
你已开通华为OD训练营权益,还差最后一步——完成入营激活(兑换课程 + 加飞书 + 登记服务群),即可解锁全部课程与专属服务。去激活 →
← 返回题库

K0002. 魔法流量水晶的超载警报

中等通过率 51% · 提交 278 · 通过 142
前缀和枚举滑动窗口

小慕正在维护一座名为「流量水晶」的数据监测系统,它每秒记录一次网络请求量,并存入数组 `requests` 中。当某个连续内的请求总量超过设定的时,系统就会触发一次 请求过载事件。 请求过载事件 定义如下: 在一个连续的时间窗口(窗口长度范围为 `[minWindow, maxWindow]`),如果该窗口内的请求量之和大于设定的阈值 `maxLoad`,则视为一次 请求过载事件。 注意: 1. 两个时间窗口只要起点或终点不同,就视为不同的时间窗口。 2. 保证请求过载事件的总次数不超过 100,000 次。 请计算小慕的系统触发了多少次请求过载事件。

提示:带虚线的词点一下有通俗解释。

输入描述

第一行输入一个整数 `n`,表示数组 `magicFlows` 的长度,满足 `1 <= n <= 100,000`。 第二行输入 `n` 个整数,表示数组 `magicFlows`,其中 `0 <= magicFlows[i] <= 10,000`。 第三行、第四行分别输入两个整数,分别表示时间窗口的最小长度 `minWindow` 和最大长度 `maxWindow`,满足 `1 <= minWindow <= maxWindow <= n`。 第五行输入一个整数 `magicThreshold`,表示魔法超载的阈值,满足 `1 <= magicThreshold <= 10^9`。

输出描述

输出一个整数,表示发生魔法超载事件的次数。

示例

示例 1

输入

5
5 2 3 6 4
2
3
10

输出

2

说明:总计 2 次魔法超载事件:[2, 3, 6], [3, 6, 4]

示例 2

输入

5
1 1 1 1 1
1
5
10

输出

0

示例 3

输入

10
10 9 8 7 6 5 4 3 2 1
2
5
15

输出

16

时间限制 1000 ms · 内存限制 128 MB

看不懂题目?点开图解
魔法流量水晶超载事件图解 5 2 3 6 4 0 1 2 3 4 窗口长度范围: [2, 3] 阈值: 10 窗口1: 2+3+6=11 > 10 窗口2: 3+6+4=13 > 10 共有 2 次魔法超载事件 窗口1 (下标1~3) 窗口2 (下标2~4) 每个连续窗口长度在[2,3]内,总和超过10即触发超载
写完代码点「提交」,将对全部测试用例判题。

向老师提问

针对「魔法流量水晶的超载警报」把疑问、代码和报错填清楚,老师收到后能更快、更准地回复你。