算法

(单调队列) $\mathcal{O}(n)$

• 先选区间再清零，必然会将选定区间和最大的一段清零
• 选择的区间 $[l, r]$ 可行，相当于清零操作后 $[l, r]$ 的区间和 $\leqslant p$
• 针对每一个 $r$，求出最小的 $l$，使得 $[l, r]$ 可行。当 $r$ 增加时，$l$ 也单调增加。
• 如何确定 $[l, r]$ 是否可行？关键在于找出 $[l, r]$ 中长度为 $d$ 的最大子区间和。
• 求前缀和 $s$ 后，相关于问 $\max\{s[j]-s[j-d]\}, l+d-1 \leqslant j \leqslant r$，单调队列

C++ 代码

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)

using namespace std;
using ll = long long;

int main() {
    cin.tie(nullptr) -> sync_with_stdio(false);

    int n, d; ll p;
    cin >> n >> p >> d;

    vector<int> a(n);
    rep(i, n) cin >> a[i];
    vector<ll> s(n+1);
    rep(i, n) s[i+1] = s[i]+a[i];

    auto sum = [&](int i) { return s[i] - s[i-d]; };

    deque<int> q;
    int l = 1, ans = 0;
    for (int r = d; r <= n; ++r) {
        while (q.size() and sum(q.back()) < sum(r)) q.pop_back();
        q.push_back(r);
        while (s[r]-s[l-1] - sum(q.front()) > p) {
            ++l;
            // [l, l+d-1] 不在 [l+1, r] 范围内
            while (q.size() and q.front() < l+d-1) q.pop_front();
        }
        ans = max(ans, r-l+1);
    }

    cout << ans << '\n';

    return 0;
}