Nemlit 的博客

Nemlit 的博客

By a konjac

题解 P3594 【[POI2015]WIL-Wilcze doły】

posted on 2019-09-20 19:24:05 | under 题解 |

定义 $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;
}