[HOJ] 127 移方塊

跟這題的做法有點像
把前綴分別由後往前和由前往後做成單調序列
有點貪心的觀念

#include<cstdio>
#include<cstdlib>
#include<algorithm>
#define MAX 1000005
using namespace std;
int l[MAX],r[MAX],n,m,li,ri,ptl,ptr,ans;
bool fr;
long long sum[MAX],a[MAX],k;
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%lld",&k);
        sum[i]=sum[i-1]+k;
    }
    while(m--){
        ans=li=ri=ptr=ptl=0;
        scanf("%lld",&k);
        for(int i=1;i<=n;i++)
            a[i]=sum[i]-k*i;
        for(int i=1;i<=n;i++){
            while(li&&a[l[li]]<=a[i])li--;
            l[++li]=i;
        }
        r[0]=n;
        for(int i=n-1;i>=0;i--){
            while(ri&&a[r[ri]]>=a[i])ri--;
            r[++ri]=i;
        }
        ptr=ri;
        while(ptl<=li&&ptr>=0){
            if(a[l[ptl]]>=a[r[ptr]]){
                ans=max(ans,l[ptl]-r[ptr]);
                ptl++;
            }
            else ptr--;
        }
        if(fr)printf(" %d",ans);
        else printf("%d",ans);
        fr=true;
    }
}