[POI2015]WIL-Wilcze do?y

定义\(sum[x] = \sum_{i = 1}^x a[i]\)

首先不难想到，我们枚举左右端点，然后贪心的减去这一段区间中\(sum[x] - sum[x - d + 1]\)的最大值，这样枚举是\(O(N^3)\)的

然后我们发现，对于一个左端点，我们肯定要尽可能的往后去找右端点，同理，对于一个右端点，我们肯定要尽可能找满足条件的最偏左的左端点

可以把枚举改成双指针，复杂度变成了\(O(N^2)\)

我们重新来看一下题意的式子：枚举右端点\(r\)，找到\(max(sum[r] - sum[l - 1] - max(sum[x] + sum[x - d + 1]))\)的值

我们复杂度的瓶颈在于维护\(max(sum[x] + sum[x - d + 1])\)，不难发现这个式子是单调的，所以我们可以使用单调队列来维护

右指针每次往右边移动的时候，把\(max(sum[x] + sum[x - d + 1])\)加入队列并弹出不单调的值

如果当前队列的最大值（队首）所对应的端点比我们求出的左端点小了，就可以弹出了

#include<bits/stdc++.h>
using namespace std;
#define il inline
#define re register
#define int long long
il int read() {
    re int x = 0, f = 1; re char c = getchar();
    while(c < '0' || c > '9') { if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - 48, c = getchar();
    return x * f;
}
#define rep(i, s, t) for(re int i = s; i <= t; ++ i)
#define maxn 2000005
int n, p, d, ans, a[maxn], l, sum[maxn], h, t, q[maxn];
signed main() {
    n = read(), p = read(), d = read();
    rep(i, 1, n) a[i] = read(), sum[i] = sum[i - 1] + a[i];
    ans = d, q[t] = d, l = 1;
    rep(i, d + 1, n) {
        while(h <= t && sum[i] - sum[i - d] > sum[q[t]] - sum[q[t] - d]) -- t;
        q[++ t] = i;
        while(h <= t && sum[i] - sum[l - 1] - sum[q[h]] + sum[q[h] - d] > p) {
            ++ l;
            while(h <= t && q[h] - d + 1 < l) ++ h;
        }
        ans = max(ans, i - l + 1);
    }
    printf("%lld", ans);
    return 0;
}

[POI2015]WIL-Wilcze do?y

原文：https://www.cnblogs.com/bcoier/p/11618374.html