Luogu 3594 [POI2015]WIL-Wilcze doły

简单题。

考虑没有修改数字的条件的限制，我们直接用双指针扫描就可以计算出答案了。

然后考虑加入修改数字的条件，只要用单调队列维护出当前两个指针表示的区间中长度为$d$的一段区间的最大值，用总和减掉这个最大值更新答案即可。

时间复杂度$O(n)$。

Code：

#include <cstdio>
#include <cstring>
using namespace std;
typedef long long ll;

const int N = 2e6 + 5;

int n, d, q[N];
ll lim, a[N], sum[N];

template <typename T>
inline void read(T &X) {
    X = 0; char ch = 0; T op = 1;
    for(; ch > '9'|| ch < '0'; ch = getchar())
        if(ch == '-') op = -1;
    for(; ch >= '0' && ch <= '9'; ch = getchar())
        X = (X << 3) + (X << 1) + ch - 48;
    X *= op;
}

inline void chkMax(int &x, int y) {
    if(y > x) x = y;
}

int main() {
    read(n), read(lim), read(d);
    for(int i = 1; i <= n; i++) {
        read(a[i]);
        sum[i] = sum[i - 1] + a[i];
    }
    
    int l = 1, r = 0, last = 0, ans = d;
    for(int i = d; i <= n; i++) {
        for(; l <= r && sum[i] - sum[i - d] > sum[q[r]] - sum[q[r] - d]; --r);
        q[++r] = i;
        for(; l <= r && q[l] - d < last; ++l);
        for(; l <= r && sum[i] - sum[last] - sum[q[l]] + sum[q[l] - d] > lim; ) {
            ++last;
            for(; l <= r && q[l] - d < last; ++l);
        }
        chkMax(ans, i - last);
    }

    printf("%d\n", ans);
    return 0;
}

View Code

Luogu 3594 [POI2015]WIL-Wilcze doły

推荐阅读