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

Nemlit

2019-09-20 19:24:05

Solution

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