2026 华为OD机试真题 8月2日华为OD上机新系统考试真题 200 分题型

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

题目描述

你为一款动作游戏设计战士角色的技能：战士每个技能会消耗不同能量，释放技能有 2 个约束：连续释放技能数量不能超过 m 个，技能能量总和不能超过能量上限 k；如果超过则必须中断当前技能，进入调息状态（即分段）。

战士有一项爆发技巧：在单次战斗中有一次能量上限翻倍至 2k 的机会，此项场景下战士需使用连续的 w 个技能（技能数量限制 m 依然生效）。

任务目标：

作为战术分析师，你需要为战士规划最优的技能释放序列。给定一套技能的能量消耗列表 a，请计算在合理使用爆发机会（或选择不使用）的前提下，释放完所有技能所需的最少分段数（即最少调息次数）。

若存在某个技能的能耗过高，即使开启爆发也无法释放（大于 2k），则判定为无解，返回 −1。

2026 华为OD机试真题 8月2日华为OD上机新系统考试真题 200 分题型

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

输入描述

输入参数说明：

• k: 能量上限，正整数
• m: 单次调息最大技能数，正整数
• w: 爆发持续技能数，正整数
• a: 技能能量消耗列表，长度为 n，每个元素为正整数

输入为一行，格式为：

k,m,w,[a1,a2,...,an]

数组中允许出现空格，例如 [1, 1, 1]。

数据范围：

• n 为技能数量，即 a 的长度
• 1≤w≤n
• 1≤n≤100000
• 1≤m≤n
• 1≤k≤1000000000
• 1≤a[i]≤1000000000

输出描述

输出满足条件的最少分段数（最少调息次数）。若无解则输出 −1。

示例1

输入

5,3,2,[3,4,3,4]

输出

3

说明

爆发窗口覆盖索引 0∼1 [3,4] 为 1 段，剩余 [3],[4] 各 1 段 → 共 3 段。

示例2

输入

10,5,3,[1, 1, 1, 1, 1]

输出

1

说明

sum(a)=5≤k=10 且 n=5≤m=5，无需爆发即可 1 段放完。若开启爆发，窗口最多覆盖 w=3 个技能，剩余 1 个技能需另开 1 段，反而变成 2 段，因此不使用爆发更优。

解题思路

核心思想

普通释放时，每一段最多包含 m 个技能，且能量和不超过 k。由于所有技能能耗都是正数，对于固定右端点，最后一段越长越不差，因此可以用滑动窗口在线性时间内求出前缀最少分段数；同理从右往左求后缀最少分段数。

爆发只能使用一次，并且必须覆盖连续 w 个技能，这 w 个技能单独作为一个分段，能量上限为 2k，技能数量限制仍为 m。枚举爆发窗口位置，答案为：

窗口左侧普通最少段数 + 1 + 窗口右侧普通最少段数

同时还要和“不使用爆发”的方案取最小值。

算法步骤

1. 如果存在 a[i] > 2k，即使爆发也无法释放，直接返回 -1。
2. 用滑动窗口构造 prefix[i]：普通状态下释放前 i 个技能的最少分段数。
3. 用反向滑动窗口构造 suffix[i]：普通状态下释放 a[i...n-1] 的最少分段数。
4. 初始答案为 prefix[n]，表示完全不使用爆发。
5. 若 w <= m，枚举每个长度为 w 的窗口；当窗口能量和不超过 2k 且左右两侧都能普通释放时，更新答案。
6. 若最终仍无法释放，输出 -1，否则输出最小分段数。

复杂度分析

设技能数量为 n。

• 时间复杂度：O(n)，前缀、后缀和爆发窗口各线性扫描一次。
• 空间复杂度：O(n)，用于保存 prefix 和 `suff