1. 题意整理

你要从某个位置出发，向右连续通过一段关卡。

• 每个关卡的士气变化是 。
• 初始士气为 。
• 过程中，士气值不能低于 。
• 你最多可以把 个负数关卡的影响直接豁免，也就是把这些负数当成 。

要求的是：最长能通过多少个连续关卡。

2. 先想清楚一个固定起点怎么判断能不能通过

假设我们固定起点是 ，现在向右枚举终点 。

我们关心的是：区间 能不能在最多 次豁免后变成“每一步士气都不低于 ”。

最自然的做法是，从左到右扫描这段区间：

• 如果当前关卡是正数，士气会增加，直接加上去。
• 如果当前关卡是负数，它会让士气下降。
• 如果某一刻士气变成负数，说明这段前缀已经不合法了，必须立刻使用一次豁免，把前面某个负数关卡的影响取消掉。

为什么要取消“最狠”的那个负数？

因为我们希望当前士气尽量大，这样后面的关卡更容易通过。

所以，当你要从已经出现的负数里选一个来豁免时，应该选绝对值最大的那个负数。这样能把士气提升得最多。

这就是一个经典的贪心：

• 扫描到哪里，就把已经遇到的负数先放进一个堆里。
• 一旦士气掉到负数，就从堆里拿出“最负”的那个来豁免。

3. 对固定起点的做法

对于每一个起点 ：

1. 令当前士气 sum = 0。
2. 从左到右枚举 。
3. 把 加入 sum。
4. 如果 ，就把它的绝对值放进一个大根堆。
5. 只要 sum < 0，就从堆里取出最大的负数取消它的影响，直到 sum >= 0 或者已经用完 次豁免。
6. 如果最终 sum >= 0，说明区间 合法，可以更新答案。
7. 如果用了 次以后还是负数，说明以 为起点，继续往右已经不可能了，可以直接停止这一轮枚举。

4. 为什么这个贪心是对的？

我们只要保证两个事实：

事实 1：一旦某个前缀士气变成负数，这个前缀就一定不合法。

因为题目要求的是“任何时刻都不能低于 ”。

事实 2：当必须使用一次豁免时，取消绝对值最大的负数一定最优。

设当前已经遇到的负数里，有两个负数 和 ，并且 。

• 取消 可以让士气增加 。
• 取消 只能让士气增加 。

显然 更大，取消它只会让当前士气更高，不会更差。

而当前士气更高，只会让后面的判断更容易通过，所以这个选择不会比别的选择差。

因此，这个贪心是正确的。

5. 复杂度分析

对于每个起点 ，我们最多向右扫到 个位置，每个负数最多进堆、出堆一次。

因此总复杂度是 。

题目里 ，这个复杂度完全可以通过。

6. 参考代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, K;
    cin >> N >> K;

    vector<long long> A(N);
    for (int i = 0; i < N; ++i) {
        cin >> A[i];
    }

    int ans = 0;

    for (int l = 0; l < N; ++l) {
        priority_queue<long long> pq;
        long long sum = 0;
        int used = 0;

        for (int r = l; r < N; ++r) {
            sum += A[r];
            if (A[r] < 0) {
                pq.push(-A[r]);
            }

            while (sum < 0 && used < K && !pq.empty()) {
                sum += pq.top();
                pq.pop();
                ++used;
            }

            if (sum >= 0) {
                ans = max(ans, r - l + 1);
            } else {
                break;
            }
        }
    }

    cout << ans << '\n';
    return 0;
}