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

第一篇题解确实会被讨论区里的数据hack掉，那么就随便水一个不会被hack掉的题解吧 首先我们尝试着发现这道题的一些结论，**你就会发现答案是单调的不降的** 这里的答案不降指的是**选择每一个位置$i$作为结尾能形成的最长区间的左端点是单调不降的**，这个很好证明，将$i-1$这个位置作为结尾形成的最长区间的左端点不可能比$i$作为结尾形成的最长区间的左端点更靠右 如果更靠右的话，那么$i-1$形成的区间还能更靠左一些，这与我们的假设不符，所以这个结论是成立的 之后我们就可以利用这个结论计算每一个$i$为结尾的区间的左端点在哪里了 由于$i$的左端点不可能比$i-1$的更靠左，所以我们就直接来将$i-1$的左端点$last$为起始端点就好了 如果$p[i]-p[last-1]$即这段区间的和减去这个区间内所有**长度为$d$的区间和的最大值**还是超过$p$，那么我们就让$last++$，直到满足条件为止 至于怎么维护一个区间内所有长度为$d$的区间和的最大值，我们用一个单调队列就好了 时间复杂度其实是均摊了两次，但是还是非常优秀的$O(n)$ 代码 ```cpp #include<iostream> #include<cstring> #include<queue> #include<cstdio> #define re register #define maxn 2000005 #define max(a,b) ((a)>(b)?(a):(b)) #define min(a,b) ((a)<(b)?(a):(b)) #define LL unsigned long long LL n,p,d; LL a[maxn],pre[maxn]; LL ans,t[maxn],last; inline LL read() { LL x=0; char c=getchar(); while(c<'0'||c>'9') c=getchar(); while(c>='0'&&c<='9') x=x*10+c-48,c=getchar(); return x; } int main() { n=read(); p=read(); d=read(); for(re int i=1;i<=n;i++) a[i]=read(); for(re int i=1;i<=n;i++) pre[i]=pre[i-1]+a[i]; std::deque<int> q; for(re int i=d;i<=n;i++) t[i]=pre[i]-pre[i-d];//t[i]表示[i-d+1,i]这个区间的和 ans=d;//最开始ans为d q.push_back(d); last=1; for(re int i=d+1;i<=n;i++) { while(!q.empty()&&t[i]>t[q.back()]) q.pop_back(); q.push_back(i);//在队尾加入一个元素 while(!q.empty()&&q.front()-d+1<last) q.pop_front(); //，如果队首元素的左端点比last还小，那么就弹出不合法的队首元素 while(!q.empty()&&pre[i]-pre[last-1]-t[q.front()]>p) { last++; while(!q.empty()&&q.front()-d+1<last) q.pop_front(); //last++后也要维护队首的合法性 } ans=max(ans,i-last+1); } std::cout<<ans; return 0; } ```