为什么会运行错误呢qwq

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

boy♂Next♂dooor @ 2023-10-05 12:50:49

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
int n,k;
struct node{
    int xu,w;
}a[N];
queue<node> q1;
queue<node> q2;
int ans1[N],ans2[N],top;
int main()
{
    scanf("%d %d",&n,&k);
    for(int i=1;i<=n;i++) scanf("%d",&a[i].w);
    for(int i=1;i<=n;i++) a[i].xu=i;
    for(int i=1;i<=k;i++)
    {
        q1.push(a[i]);  
        if(!q1.empty()&&a[i].w<q1.back().w)
        {
            q1.pop();q1.push(a[i]);
        }
        q2.push(a[i]);  
        if(!q2.empty()&&a[i].w>q2.back().w)
        {
            q2.pop();q2.push(a[i]);
        }
    }
    ans1[++top]=q1.back().w;ans2[top]=q2.back().w;
    for(int i=k+1;i<=n;i++)
    {
        if(!q1.empty()&&a[i].w<q1.back().w)
        {
            q1.push(a[i]);
        }       
        if(!q2.empty()&&a[i].w>q2.back().w) 
        {
            q2.push(a[i]);
        }
        while(i-q1.back().xu>=k) q1.pop();
        while(i-q2.back().xu>=k) q2.pop();
        ans1[++top]=q1.back().w;ans2[top]=q2.back().w;
    }
    for(int i=1;i<=top;i++) printf("%d ",ans1[i]);
    printf("\n");
    for(int i=1;i<=top;i++) printf("%d ",ans2[i]);
    return 0;
}

借鉴了题解中优先队列的做法，但一开始自己做的时候用了queue所以后来就直接手动比较了，但不知道哪里错了TAT

by IceKylin @ 2023-10-05 12:57:32

@boy♂Next♂dooor

while(i-q1.back().xu>=k) q1.pop();

应当先判断 q1.empty()

by boy♂Next♂dooor @ 2023-10-05 15:11:04

@IceKylin

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
int n,k;
struct node{
    int xu,w;
}a[N];
queue<node> q1;
queue<node> q2;
int ans1[N],ans2[N],top;
int main()
{
    scanf("%d %d",&n,&k);
    for(int i=1;i<=n;i++) scanf("%d",&a[i].w);
    for(int i=1;i<=n;i++) a[i].xu=i;
    for(int i=1;i<=k;i++)
    {
        q1.push(a[i]);  
        if(!q1.empty()&&a[i].w<q1.back().w)
        {
            q1.pop();q1.push(a[i]);
        }
        q2.push(a[i]);  
        if(!q2.empty()&&a[i].w>q2.back().w)
        {
            q2.pop();q2.push(a[i]);
        }
    }
    ans1[++top]=q1.back().w;ans2[top]=q2.back().w;
    for(int i=k+1;i<=n;i++)
    {
        if(!q1.empty()&&a[i].w<q1.back().w)
        {
            q1.push(a[i]);
        }       
        if(!q2.empty()&&a[i].w>q2.back().w) 
        {
            q2.push(a[i]);
        }
        while(!q1.empty()&&i-q1.back().xu>=k) q1.pop();
        while(!q2.empty()&&i-q2.back().xu>=k) q2.pop();
        ans1[++top]=q1.back().w;ans2[top]=q2.back().w;
    }
    for(int i=1;i<=top;i++) printf("%d ",ans1[i]);
    printf("\n");
    for(int i=1;i<=top;i++) printf("%d ",ans2[i]);
    return 0;
}

倒是不运行错误了，但是WA了，样例都过不了.....

by boy♂Next♂dooor @ 2023-10-07 16:22:13

@IceKylin 我发现好像用queue做不了，要是存一串数不知道怎么存，只存一个最大最小值又无法比较距离....

by IceKylin @ 2023-10-07 18:59:29

@boy♂Next♂dooor

建议学树状数组

by HugeSB @ 2023-10-10 18:28:37

@boy♂Next♂dooor STL里有个deque，就是解决这个问题的双端队列这个