目录
题目
思路
Code
题目
题目内容：
你为一款动作游戏设计战士角色的技能。战士每个技能会消耗不同能量，释放技能有两个约束：连续释放技能数量不能超过 m 个，技能能量总和不能超过能量上限 k；如果超过则必须中断当前技能，进入调息状态，也就是分段。
战士有一项爆发技巧，在单次战斗中有一次能量上限翻倍至 2k 的机会。此项场景下战士需使用连续的 w 个技能，技能数量限制 m 依然生效。
作为战术分析师，你需要为战士规划最优的技能释放序列。给定一套技能的能量消耗列表 a，请计算在合理使用爆发机会或选择不使用的前提下，释放完所有技能所需的最少分段数，也就是最少调息次数。
若存在某个技能的能耗过高，即使开启爆发也无法释放，即大于 2k，则判定为无解，返回 -1。
输入描述：
第一行输入三个正整数 k、m、w。k 表示能量上限，m 表示单次调息最大技能数，w 表示爆发持续技能数。
第二行输入技能能量消耗列表 a，元素之间使用英文逗号分隔。技能数量 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
输入：
5 3 2 6,1,2,3输出：
2说明：
技能 6 大于 k 且小于 2k，必须靠爆发窗口覆盖才有解。
样例 3
输入：
10 5 3 1,1,1,1,1输出：
1说明：
所有技能无需爆发即可一段放完，使用爆发反而会把序列切开，因此不使用爆发更优。
思路
整体思路：最多只有一次爆发。答案要么是不使用爆发时的最少分段数，要么是某个长度为 w 的连续窗口使用爆发时，左侧普通分段数加上爆发段 1 加上右侧普通分段数。
第一步：先检查是否存在 a[i] 大于 2k，若存在则任何情况下都无法释放，直接返回 -1。
第二步：用贪心计算普通能量上限 k 下的前缀分段数组 pre。pre[i] 表示释放前 i 个技能所需的最少段数。每段尽量放入更多技能，遇到技能数超过 m 或能量和超过 k 时新开一段。
第三步：同理从右到左计算后缀分段数组 suf。suf[i] 表示释放 i 到末尾这些技能所需的最少段数。
第四步：不使用爆发的答案为 pre[n]。若 w 大于 m，爆发窗口不满足技能数量限制，不能使用爆发。
第五步：滑动枚举长度为 w 的窗口，窗口能量和不超过 2k 时才合法。合法窗口的候选答案为 pre[left] + 1 + suf[right+1]，取最小值。
复杂度分析：前缀、后缀和滑动窗口都只扫描一遍数组，时间复杂度 O(n)，空间复杂度 O(n)。
Code
import sys INF = 10 ** 9 def prefix(a, limit, m): res = [INF] * (len(a) + 1) res[0] = 0 total = cnt = seg = 0 # 输入包含普通能量上限、单段技能数上限和爆发窗口长度。 for i, value in enumerate(a): if value > limit: # 任意单个技能超过 2k 时，爆发也无法释放，直接无解。 return res if cnt + 1 > m or total + value > limit: seg += 1 total = 0 cnt = 0 total += value cnt += 1 res[i + 1] = seg + 1 # 普通分段按顺序贪心装入技能，得到每个前缀的最少段数。 return res def suffix(a, limit, m): n = len(a) res = [INF] * (n + 1) res[n] = 0 total = cnt = seg = 0 # 后缀数组用同样逻辑从右往左计算，方便枚举爆发窗口。 for i in range(n - 1, -1, -1): value = a[i] # 每段同时受技能数量 m 和能量上限 k 两个条件约束。 if value > limit: return res # 爆发窗口长度必须不超过 m，否则技能数量限制已经不合法。 if cnt + 1 > m or total + value > limit: seg += 1 total = 0 cnt = 0 total += value cnt += 1 res[i] = seg + 1 # 滑动窗口维护连续 w 个技能的能量总和。 return res def solve(k, m, w, a): # 窗口能量不超过 2k 时，才可以作为一次合法爆发段。 if any(value > 2 * k for value in a): return -1 pre = prefix(a, k, m) suf = suffix(a, k, m) # 候选答案由左侧普通段、一个爆发段和右侧普通段相加得到。 ans = pre[len(a)] if w > m: return -1 if ans == INF else ans total = 0 left = 0 for right, value in enumerate(a): total += value while left <= right and (right - left + 1 > w or total > 2 * k): total -= a[left] left += 1 if right - left + 1 == w and pre[left] != INF and suf[right + 1] != INF: ans = min(ans, pre[left] + 1 + suf[right + 1]) return -1 if ans == INF else ans first, second = sys.stdin.read().strip().splitlines() k, m, w = map(int, first.split()) a = list(map(int, second.split(','))) print(solve(k, m, w, a))JS
const fs = require('fs'); // 输入包含普通能量上限、单段技能数上限和爆发窗口长度。 const lines = fs.readFileSync(0, 'utf8').trim().split(/\n/); const [k, m, w] = lines[0].trim().split(/\s+/).map(Number); // 任意单个技能超过 2k 时，爆发也无法释放，直接无解。 const a = lines[1].trim().split(',').map(Number); const INF = 1e9; function calc(reverse) { const res = new Array(a.length + 1).fill(INF); // 普通分段按顺序贪心装入技能，得到每个前缀的最少段数。 if (!reverse) { res[0] = 0; let sum = 0; let count = 0; let segments = 0; // 后缀数组用同样逻辑从右往左计算，方便枚举爆发窗口。 for (let i = 0; i < a.length; i++) { if (a[i] > k) return res; // 每段同时受技能数量 m 和能量上限 k 两个条件约束。 if (count + 1 > m || sum + a[i] > k) { segments++; sum = 0; count = 0; } sum += a[i]; count++; res[i + 1] = segments + 1; } } else { res[a.length] = 0; let sum = 0; let count = 0; let segments = 0; // 爆发窗口长度必须不超过 m，否则技能数量限制已经不合法。 for (let i = a.length - 1; i >= 0; i--) { if (a[i] > k) return res; // 滑动窗口维护连续 w 个技能的能量总和。 if (count + 1 > m || sum + a[i] > k) { segments++; sum = 0; count = 0; } sum += a[i]; count++; res[i] = segments + 1; } } // 窗口能量不超过 2k 时，才可以作为一次合法爆发段。 return res; } // 候选答案由左侧普通段、一个爆发段和右侧普通段相加得到。 if (a.some((value) => value > 2 * k)) { console.log(-1); } else { const pre = calc(false); const suf = calc(true); let ans = pre[a.length]; if (w <= m) { let sum = 0; let left = 0; for (let right = 0; right < a.length; right++) { sum += a[right]; while (left <= right && (right - left + 1 > w || sum > 2 * k)) { sum -= a[left]; left++; } if (right - left + 1 === w && pre[left] !== INF && suf[right + 1] !== INF) { ans = Math.min(ans, pre[left] + 1 + suf[right + 1]); } } } console.log(ans === INF ? -1 : ans); }【华为od机试真题Python+JS+Java+Go合集】【超值优惠】：Py/JS/Java/Go合集
【华为od机试真题Python】：Python真题题库
【华为od机试真题JavaScript】：JavaScript真题题库
【华为od机试真题Java&Go】：Java&Go真题题库
【华为od机试真题C++】：C++真题题库
【华为od机试真题C语言】：C语言真题题库
【华为od面试手撕代码题库】：面试手撕代码题库
【华为od机试面试交流群】【文章底部有二维码链接，可扫码加交流群】
华为OD机试:二本院校有机会吗? 有机会,但不大,大神除外!机考分数越高越好,所以需要提前刷题。机考通过后,如果没有收到面试邀请,也不要着急,非目标院校面试邀请发的时间比较晚。非目标院校今年有点难,机试至少要考到350分,所以需要疯狂刷题,华为OD机考是有题库的,最好在考前完所有题库题目。华为OD机试:跨专业可以参加华为OD可以,但是如果你的本科院校比较差,上岸概率不大。华为OD机试:华为OD简历被锁定机试通过,性格测试也通过,但是没人联系面试,发现简历被锁定。此时需要主动去联系HR。让他帮助你查询原因。
