2026 华为OD机试真题9月26日华为OD上机新系统考试真题 100 分题型

点击查看华为 OD 机试真题完整目录：2026最新华为OD机试新系统卷 + 双机位C卷 真题题库目录｜全覆盖题库 + 逐点算法考点详解

题目描述

数据中心使用一个整数数组 scores，记录 $N$ 小时内每小时的服务器得分（可正可负）。$0$ 表示服务器故障（无效小时）。

你需要找到一个连续子数组作为维护窗口，满足以下条件：

1. 子数组中不包含任何 $0$；
2. 子数组长度 $L$ 不能超过指定上限 $W$（$1 \le L \le W$），且子数组元素之和最小；
3. 如果存在多个满足上述条件的子数组，选择起始下标最小的那个。

2026 华为OD机试真题9月26日华为OD上机新系统考试真题 100 分题型

点击查看华为 OD 机试真题完整目录：2026最新华为OD机试新系统卷 + 双机位C卷 真题题库目录｜全覆盖题库 + 逐点算法考点详解

输入描述

$N$：总小时数（$1 \le N \le 100000$）；

$W$：窗口长度（$1 \le W \le \min(N, 10000)$）；

scores：长度为 $N$ 的整数数组，表示每小时的得分。

输出描述

一个包含两个整数的数组 [start_index, min_sum]，其中 start_index 是子数组的起始下标（从 $0$ 开始），min_sum 是最小和。

如果不存在满足条件的子数组（如数组全为 $0$），返回 [-1, 0]。

示例1

输入

4
3
0,0,0,0

输出

[-1,0]

说明

• 窗口大小最小为 $1$，最大为 $3$，且不能包含 $0$。
• 所有得分都是 $0$，因此无解，返回 [-1,0]。

示例2

输入

4
3
-10,5,-10,5

输出

[0,-15]

说明

• 窗口最大为 $3$。
• 从下标 $0$ 开始的连续 $3$ 个小时的总和为 $-10+5+(-10) = -15$，为得分最小的窗口。

示例3

输入

6
3
-3,0,-5,-2,0,-6

输出

[2,-7]

说明

• 窗口最大为 $3$，且 $0$ 不能包含在窗口内。
• 所以类似从下标 $0$ 开始的 -3,0,-5 不能构成连续窗口。
• 得分最小的连续窗口是从下标 $2$ 开始的 $-5+(-2) = -7$。

解题思路

本题采用【前缀和 + 单调队列】算法：设 prefix[i] 表示前 i 个小时的得分和。对于固定的右端点 r，合法窗口左端点 l 必须位于当前连续非零段内，并满足 r-W+1 <= l <= r，窗口和为 prefix[r+1]-prefix[l]。要让窗口和最小，就需要在所有合法左端点中找到最大的 prefix[l]。

使用单调队列保存可能成为左端点的前缀下标，并让对应的前缀和值从队首到队尾单调不增。每次先移除已经超出长度限制的下标，再加入当前下标 r；队首就是当前最大的合法前缀和。维护队列时只弹出严格更小的前缀和，这样前缀和相等时会保留更早的下标，能够满足最小和相同时选择起点最小的要求。

遇到得分为 的小时后，任何合法窗口都不能跨过该位置，因此清空队列并更新当前非零段起点。如果遍历结束后没有处理过任何非零元素，则返回 `[-1,