14. 战士技能规划设计[200分]

题目内容

你为一款动作游戏设计战士角色的技能：战士每个技能会消耗不同能量，释放技能有 2 个约束：

• 连续释放技能数量不能超过 $m$ 个
• 技能能量总和不能超过能量上限 $k$

如果超过则必须中断当前技能，进入调息状态（即分段）。

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

任务目标： 作为战术分析师，你需要为战士规划最优的技能释放序列。给定一套技能的能量消耗列表 $a$，请计算在合理使用爆发机会（或选择不使用）的前提下，释放完所有技能所需的最少分段数（即最少调息次数）。若存在某个技能的能耗过高，即使开启爆发也无法释放（大于 $2k$），则判定为无解，返回 $-1$。

输入描述

输入参数说明：

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

数据范围：

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

输出描述

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

样例

样例 1

输入

5 3 2
3,4,3,4

输出

3

说明： 爆发窗口覆盖索引 $0 \sim 1$ 的 [3,4] 为 1 段，剩余 [3]、[4] 各 1 段 $\to$ 共 3 段。

样例 2

输入

5 3 2
6,1,2,3

输出

2

说明： $a[0] = 6 > k = 5$ 且 $a[0] < 2k = 10$，必须靠爆发窗口覆盖 $a[0]$ 才有解。

样例 3

输入

10 5 3
1,1,1,1,1

输出

1

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

代码

const readline = require('readline');
const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout,
});

let lines = [];
rl.on('line', (input) => {
    lines.push(input);
    if (lines.length === 2) {
        // 解析输入
        const [k, m, w] = lines[0].split(' ').map(Number);
        const a = lines[1].split(',').map(Number);
        const n = a.length;
        
        // ========== 无解判断 ==========
        // 如果某个技能大于2k，即使开启爆发也无法释放
        for (let v of a) {
            if (v > 2 * k) {
                console.log(-1);
                return;
            }
        }
        
        // ========== 核心函数：计算从某位置开始最多能放几个技能 ==========
        function getMaxLen(start, limitK) {
            let sum = 0;      // 当前段累计能量
            let cnt = 0;      // 当前段技能数量
            
            for (let i = start; i < n; i++) {
                // 约束1：技能数量不能超过m
                if (cnt + 1 > m) break;
                
                // 约束2：能量总和不能超过limitK
                if (sum + a[i] > limitK) break;
                
                sum += a[i];
                cnt++;
            }
            return cnt;
        }
        
        // ========== 计算不爆发时的最少分段数 ==========
        function calcSegments(limitK) {
            let seg = 0;
            let i = 0;
            
            while (i < n) {
                let len = getMaxLen(i, limitK);
                
                // 如果len=0，说明当前技能大于limitK，无法放入任何段
                if (len === 0) return Infinity;
                
                seg++;      // 新开一段
                i += len;   // 跳过已放的技能
            }
            return seg;
        }
        
        // ========== 情况1：不使用爆发 ==========
        let ans = calcSegments(k);
        
        // ========== 情况2：使用爆发 ==========
        // 枚举爆发窗口的起始位置
        for (let start = 0; start < n; start++) {
            // 检查是否有足够的技能
            if (start + w > n) break;
            
            // ---- 检查爆发窗口是否可行 ----
            let sum = 0;
            let canBurst = true;
            
            // 检查从start开始的w个技能
            for (let i = start; i < start + w; i++) {
                sum += a[i];
                if (sum > 2 * k) {
                    canBurst = false;
                    break;
                }
            }
            
            // 如果窗口不可行，跳过
            if (!canBurst) continue;
            
            // ---- 计算使用爆发时的总分段数 ----
            let seg = 0;
            let i = 0;
            
            // 1) 爆发前的部分（使用正常能量k）
            while (i < start) {
                let len = getMaxLen(i, k);
                if (len === 0) {
                    seg = Infinity;
                    break;
                }
                seg++;
                i += len;
            }
            
            if (seg === Infinity) continue;
            
            // 2) 爆发窗口（单独一段），固定w个技能
            seg++;
            i = start + w;  // 跳过爆发窗口
            
            // 3) 爆发后的部分（使用正常能量k）
            while (i < n) {
                let len = getMaxLen(i, k);
                if (len === 0) {
                    seg = Infinity;
                    break;
                }
                seg++;
                i += len;
            }
            
            // 更新最优解
            if (seg < ans) {
                ans = seg;
            }
        }
        
        // ========== 输出结果 ==========
        console.log(ans === Infinity ? -1 : ans);
    }
});