EZOJ #88

传送门

分析

自然想到二分

我们二分一个长度，之后考虑如何线性判断是否合法

我们可以维护一个单调队列表示从i开始的长度为d的区间和的最大值

每次用一段区间和减去它包含的长度为d的区间最大值即可

但是我们发现这个数据范围有那么一点点会t的征兆

于是我们考虑消除掉二分的log

于是我们继续用单调队列维护，用双指针扫一下就可以了

代码

#include<iostream>

#include<cstdio>

#include<cstring>

#include<string>

#include<algorithm>

#include<cctype>

#include<cmath>

#include<cstdlib>

#include<queue>

#include<ctime>

#include<vector>

#include<set>

#include<map>

#include<stack>

using namespace std;

inline int ra(){

    int x=,f=;char s=getchar();

    while(!isdigit(s)){if(s=='-')f=-;s=getchar();}

    while(isdigit(s))x=(x<<)+(x<<)+(s-''),s=getchar();

    return x*f;

}

inline long long ra2(){

    long long x=,f=;char s=getchar();

    while(!isdigit(s)){if(s=='-')f=-;s=getchar();}

    while(isdigit(s))x=(x<<)+(x<<)+(s-''),s=getchar();

    return x*f;

}

long long pre[],del[],a[],q[],m;

int id[],fi,tl;

int n,d;

int main(){

    int i,j=,k;

    n=ra(),m=ra2(),d=ra();

    for(i=;i<=n;i++)a[i]=ra2();

    for(i=;i<=n;i++)pre[i]=pre[i-]+a[i];

    for(i=;i<=n-d+;i++)del[i]=pre[i+d-]-pre[i-];

    int Ans=;

    fi=,tl=;

    q[tl]=del[];

    for(i=d;i<=n;i++){

      while(tl>=fi&&q[tl]<=del[i-d+])tl--;

      q[++tl]=del[i-d+];

      id[tl]=i-d+;

      for(j;j<=i;j++){

        while(id[fi]<j)fi++;

        long long x=q[fi];

        if(pre[i]-pre[j-]-x<=m){

          Ans=max(Ans,i-j+);

          break;

        }

      }

    }

    printf("%d\n",Ans);

    return ;

}

巴特西

EZOJ #88

最新文章

热门文章