目录题目思路Code题目题目内容你为一款动作游戏设计战士角色的技能。战士每个技能会消耗不同能量释放技能有两个约束连续释放技能数量不能超过 m 个技能能量总和不能超过能量上限 k如果超过则必须中断当前技能进入调息状态也就是分段。战士有一项爆发技巧在单次战斗中有一次能量上限翻倍至 2k 的机会。此项场景下战士需使用连续的 w 个技能技能数量限制 m 依然生效。作为战术分析师你需要为战士规划最优的技能释放序列。给定一套技能的能量消耗列表 a请计算在合理使用爆发机会或选择不使用的前提下释放完所有技能所需的最少分段数也就是最少调息次数。若存在某个技能的能耗过高即使开启爆发也无法释放即大于 2k则判定为无解返回 -1。输入描述第一行输入三个正整数 k、m、w。k 表示能量上限m 表示单次调息最大技能数w 表示爆发持续技能数。第二行输入技能能量消耗列表 a元素之间使用英文逗号分隔。技能数量 n 为 a 的长度。数据范围为 1 w n1 n 1000001 m n1 k 10000000001 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[right1]取最小值。复杂度分析前缀、后缀和滑动窗口都只扫描一遍数组时间复杂度 O(n)空间复杂度 O(n)。Codeimport 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))JSconst 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机试真题PythonJSJavaGo合集】【超值优惠】Py/JS/Java/Go合集【华为od机试真题Python】Python真题题库【华为od机试真题JavaScript】JavaScript真题题库【华为od机试真题JavaGo】JavaGo真题题库【华为od机试真题C】C真题题库【华为od机试真题C语言】C语言真题题库【华为od面试手撕代码题库】面试手撕代码题库【华为od机试面试交流群】【文章底部有二维码链接可扫码加交流群】华为OD机试:二本院校有机会吗? 有机会,但不大,大神除外!机考分数越高越好,所以需要提前刷题。机考通过后,如果没有收到面试邀请,也不要着急,非目标院校面试邀请发的时间比较晚。非目标院校今年有点难,机试至少要考到350分,所以需要疯狂刷题,华为OD机考是有题库的,最好在考前完所有题库题目。华为OD机试:跨专业可以参加华为OD可以,但是如果你的本科院校比较差,上岸概率不大。华为OD机试:华为OD简历被锁定机试通过,性格测试也通过,但是没人联系面试,发现简历被锁定。此时需要主动去联系HR。让他帮助你查询原因。