求助SOS,90分,第三个点WA了

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

NaN_HQJ2007_NaN @ 2019-11-10 20:47:27

#include<bits/stdc++.h>
using namespace std;
struct note{
    int s,id;
};
const int maxn=1000000+5;
int n,k,i,j,ys,mi[maxn],ma[maxn];
note qmin[maxn];
note qmax[maxn];
int main(){
    cin>>n>>k;
    int head=1,tail=0,head2=1,tail2=0,z=0,z2=0;
    for(i=1;i<=n;i++){
        scanf("%d",&ys);
        if(i-qmin[head].id>=k){
            head++;
        }
        while(qmin[tail].s>=ys && tail-head>=0){
            tail--;
        }
        qmin[++tail].s=ys;
        qmin[tail].id=i;
        if(i>=k){
            mi[++z]=qmin[head].s;
        }
        //////////
        /////////
        if(i-qmax[head2].id>=k){
            head2++;
        }
        while(qmax[tail2].s<=ys && tail2-head2>=0){
            tail2--;
        }
        qmax[++tail2].s=ys;
        qmax[tail2].id=i;
        if(i>=k){
            ma[++z2]=qmax[head2].s;
        }
    }
    for(i=1;i<=z;i++){
        cout<<mi[i]<<" ";
    }
    cout<<endl;
    for(i=1;i<=z2;i++){
        cout<<ma[i]<<" ";
    }
    return 0;
}

by NaN_HQJ2007_NaN @ 2019-11-10 20:47:49

各位请积极回答


by NaN_HQJ2007_NaN @ 2019-11-10 21:02:05

给为dalao不用了


by nonanalyzer @ 2019-11-10 21:22:54

@jasonhqj

if(i-qmin[head].id>=k){ head++; }

第三个点k=1,i=1时你这里head会变成2,而tail还是1,于是qmin[1]被正确赋值但qmin[head]取不到这个值


by nonanalyzer @ 2019-11-10 21:23:36

后面head总是比tail大1,所以你输出全是0

qmax同理


by NaN_HQJ2007_NaN @ 2019-11-10 21:30:09

谢谢!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!


|