莫名其妙的WA了一个点......

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

yangruiping @ 2019-08-15 21:37:33

#include<bits/stdc++.h>
using namespace std;
struct nod{
    int num,sit;
}qx[1000006],qi[1000006];
int a[1000005],n,k,h,t;
int main(){
    scanf("%d%d",&n,&k);
    int i,j;
    for(i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    h=1,t=0;
    for(i=1;i<=n;i++){
        if(qi[h].sit<=i-k)h++;
        while(h<=t&&qi[t].num>=a[i])t--;
        qi[++t].num=a[i];
        qi[t].sit=i;
        if(i>=k)printf("%d ",qi[h].num);
    }
    cout<<endl;
    h=1,t=0;
    for(i=1;i<=n;i++){
        if(qx[h].sit<=i-k)h++;
        while(h<=t&&qx[t].num<=a[i])t--;
        qx[++t].num=a[i];
        qx[t].sit=i;
        if(i>=k)printf("%d ",qx[h].num);
    }   
    return 0;
} 

WA了第三个点

  • 蒟蒻求助qwq,求路过dalao一助......

by yangruiping @ 2019-08-15 21:44:36

@   吾皇


by    吾皇 @ 2019-08-15 21:46:48

..?


by    吾皇 @ 2019-08-15 21:52:52

if(qx[h].sit<=i-k)h++;

这一句改成

if(qx[h].sit<=i-k&&h<=t) h++;


by    吾皇 @ 2019-08-15 21:53:38

@yangruiping


by yangruiping @ 2019-08-15 21:57:38

@   吾皇 Thank you


by    吾皇 @ 2019-08-15 21:59:29

...毕竟两个while长度不一样看着恨不顺眼


by arekilldog @ 2019-08-16 13:15:08

我也wa在第三个点了。。。第三个点是毒瘤吧


|