啊啊啊啊!!!!

P1886 滑动窗口 /【模板】单调队列

lz2018 @ 2018-11-03 16:57:46

刚接触单调队列,求帮助

才30分, 手打的几组样例过了

#include<iostream> 
using namespace std;
long long l[10000001],l1[10000001],l2[10000001];
long long n,k,h,t;
void down(){
    l1[1]=l[1];t=h=1;
    for(int i=1;i<=n;i++){
        if(l[i]<=l1[h]){
            l1[i]=l[i];
            t=h=i;
        }
        else {
            int p=t;
            while(l[i]<l1[p]&&p>=h){
                l1[p]=99999999;
                p--;
            }
            l1[++t]=l[i];
        }
        if(t-h==k)h++;
        while(l1[h]==99999999&&h<=t)h++;
        if(i>=k)cout<<l1[h]<<" ";
    }
    cout<<endl;
}
void up(){
    l2[1]=l[1];t=h=1;
    for(int i=1;i<=n;i++){
        if(l[i]>=l1[h]){
            l2[i]=l[i];
            t=h=i;
        }
        else {
            int p=t;
            while(l[i]>l2[p]&&p>=h){
                l2[p]=-99999999;
                p--;
            }
            l2[++t]=l[i];
        }
        if(t-h==k)h++;
        while(l2[h]==-99999999&&h<=t)h++;
        if(i>=k)cout<<l2[h]<<" ";
    }
    cout<<endl;
}
int main(){
    cin>>n>>k;
    for(int i=1;i<=n;i++)cin>>l[i];
    down();
    up();
    return 0;
}

by lz2018 @ 2018-11-03 17:03:24

为什么没有回复-_-


by hpbl @ 2018-11-03 17:09:27

因为您的代码有点丑


by lz2018 @ 2018-11-03 17:11:32

@lhy930 我也这么觉得


by lz2018 @ 2018-11-03 17:14:39

问题已找到,本帖完结


by lz2018 @ 2018-11-03 17:20:44

忠告!!!

最大值一定要大的彻底

最小值一定要小的彻底

!!!!!!!!


|