题解 P3594 【[POI2015]WIL-Wilcze doły】
Xiefan_Guo
2019-08-11 13:09:47
首先发现答案是**单调不降的**。即选择每一个位置 $i$ 作为右端点能形成的最长区间的**左端点是单调不降的**。将 $i-1$ 这个位置作为结尾形成的最长区间的左端点不可能比 $i$ 作为结尾形成的最长区间的左端点更靠右
$sum[]$ 为数列前缀和。 $start$ 为起始左端点。如果 $sum[i]-sum[start-1]$ 即这段**区间的和**减去这个区间内所有**长度为 $d$ 的区间和的最大值**超过 $p$ ，那么我们就让 $start++$ ，直到满足条件为止。
```c
#include<bits/stdc++.h>
using namespace std;
const int maxn = 2000005;
int n, d, l, r, start, ans;
int que[maxn];
long long p, a[maxn], sum[maxn], ad[maxn];
int solve()
{
l = r = 1;
start = 1;
for(int i = d; i <= n; i++){
ad[i] = sum[i] - sum[i - d];
}
int ret = d;
que[r++] = d;
for(int i = d + 1; i <= n; i++){
while(l < r && ad[i] > ad[que[r - 1]]) r--;
que[r++] = i;
while(l < r && sum[i] - sum[start - 1] - ad[que[l]] > p){
start++;
while(l < r && que[l] - d + 1 < start) l++;
}
ret = max(ret, i - start + 1);
}
return ret;
}
int main()
{
scanf("%d%lld%d", &n, &p, &d);
for(int i = 1; i <= n; i++){
scanf("%lld", &a[i]);
sum[i] = sum[i - 1] + a[i];
}
ans = solve();
printf("%d\n", ans);
return 0;
}
```