自动搬运

查看原文

来自洛谷，原作者为

	Nemlit 自能生羽翼，何必仰云梯。

搬运于2025-08-24 21:50:32，当前版本为作者最后更新于2019-09-20 19:24:05，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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