[文章目录]
Description
给定一个长度为n的序列，你有一次机会选中一段连续的长度不超过d的区间，将里面所有数字全部修改为0。请找到最长的一段连续区间，使得该区间内所有数字之和不超过p。1<=d<=n<=2000000，0<=p<=10^16
贪心+单调队列+双指针。
假设选定了一段区间，我想清0的段一定是和最大的段。所以预处理所有的长为d的和，然后在操作的过程中单调队列求出来当前长度为d的子区间最大的和就好了。
双指针和单调队列写的时候好像都需要注意各种先后顺序，特判。发现一种写的套路，也不知道对不对。
就是进入循环第一件事先判断合不合法，如果合法更新答案+移动一次R，如果不合法，移动一次L。
这道题由于答案是合法区间最长长度，所以可以直接在移动L后移动R，因为如果移动L后合法，再移动R不合法，对答案没有贡献。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
int n,d,w[2001000],q[2001000],h=1,t,ans;
ll p,mx[2001000];
int read()
{
char ch=getchar(); int re=0;
while(ch<'0'||ch>'9') ch=getchar();
while(ch>='0'&&ch<='9')
re=(re<<1)+(re<<3)+ch-'0',ch=getchar();
return re;
}
int main()
{
scanf("%d%lld%d",&n,&p,&d);
for(int i=1;i<=n;i++) w[i]=read();
ll sum=0; for(int i=1;i<d;i++) sum+=w[i],mx[i]=sum;
for(int i=d;i<=n;i++)
{
sum=sum+w[i]-w[i-d];
mx[i]=sum;
}
int l=1,r=0; sum=0;
while(r<=n)
{
if(sum-mx[q[h]]<=p) ans=max(ans,r-l+1);
else {sum-=w[l]; l++; while(h<=t&&q[h]-d+1<l) h++;}
if(sum-mx[q[h]]<=p)
{
r++; sum+=w[r];
while(h<=t&&mx[q[t]]<=mx[r]) t--;
q[++t]=r;
}
}
printf("%d\n",ans);
return 0;
}