deque一运行就卡住了QAQ

陈刀仔 @ 2019-08-01 11:35:03

#include <iostream>
#include <cstdio>
#include <queue>
using namespace std;
const int maxn=1000050;
struct node{
    int id,data;
};
deque<node>q1,q2;
int n,k;
int a[maxn];
int main()
{
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++)
        scanf("%d",a+i);
    node tmp;
    node p;
    p.id=1;
    p.data=a[1];
    q1.push_back(p);
    for(int i=2;i<=n;i++)
    {
        tmp.id=i;
        tmp.data=a[i];
        while(q1.back().data>=a[i]&&!q1.empty())
            q1.pop_back();
        while(q1.front().id<i-k+1)
            q1.pop_front();
        q1.push_back(tmp);
        if(i>=k)
            cout<<q1.front().data<<' ';
    }
    cout<<endl;
    q2.push_back(p);
    for(int i=2;i<=n;i++)
    {
        tmp.id=i;
        tmp.data=a[i];
        while(q2.back().data<=a[i]&&!q2.empty())
            q2.pop_back();
        while(q2.front().id<i-k+1)
            q2.pop_front();
        q2.push_back(tmp);
        if(i>=k)
            cout<<q2.front().data<<' ';
    }
    cout<<endl;
    return 0;
}
/*
8 3
1 3 -1 -3 5 3 6 7
*/

by yu__xuan @ 2019-08-01 11:40:37

#include <iostream>
#include <cstdio>
#include <queue>
using namespace std;
const int maxn=1000050;
struct node{
    int id,data;
};
deque<node>q1,q2;
int n,k;
int a[maxn];
int main()
{
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++)
        scanf("%d",a+i);
    node tmp;
    node p;
    p.id=1;
    p.data=a[1];
    q1.push_back(p);
    for(int i=2;i<=n;i++)
    {
        tmp.id=i;
        tmp.data=a[i];
        while(!q1.empty()&&q1.back().data>=a[i])
            q1.pop_back();
        while(q1.front().id<i-k+1)
            q1.pop_front();
        q1.push_back(tmp);
        if(i>=k)
            cout<<q1.front().data<<' ';
    }
    cout<<endl;
    q2.push_back(p);
    for(int i=2;i<=n;i++)
    {
        tmp.id=i;
        tmp.data=a[i];
        while(!q2.empty()&&q2.back().data<=a[i])
            q2.pop_back();
        while(q2.front().id<i-k+1)
            q2.pop_front();
        q2.push_back(tmp);
        if(i>=k)
            cout<<q2.front().data<<' ';
    }
    cout<<endl;
    return 0;
}

by yu__xuan @ 2019-08-01 11:40:50

还是错的，qwq

by 陈刀仔 @ 2019-08-01 11:58:33

qwq

by 陈刀仔 @ 2019-08-01 11:59:40

我改出来了，是dev有问题

#include <iostream>
#include <cstdio>
#include <queue>
using namespace std;
const int maxn=1000050;
struct node{
    int id,data;
};
deque<node>q1,q2;
int n,k;
int a[maxn];
int main()
{
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++)
        scanf("%d",a+i);
    node tmp;
    node p;
    p.id=1;
    p.data=a[1];
    q1.push_back(p);
    if(k==1)
        cout<<a[1]<<' ';
    for(int i=2;i<=n;i++)
    {
        tmp.id=i;
        tmp.data=a[i];
        while(!q1.empty()&&q1.back().data>=a[i])
            q1.pop_back();
        while(!q1.empty()&&q1.front().id<i-k+1)
            q1.pop_front();
        q1.push_back(tmp);
        if(i>=k)
            cout<<q1.front().data<<' ';
    }
    cout<<endl;
    q2.push_back(p);
    if(k==1)
        cout<<a[1]<<' ';
    for(int i=2;i<=n;i++)
    {
        tmp.id=i;
        tmp.data=a[i];
        while(!q2.empty()&&q2.back().data<=a[i])
            q2.pop_back();
        while(!q2.empty()&&q2.front().id<i-k+1)
            q2.pop_front();
        q2.push_back(tmp);
        if(i>=k)
            cout<<q2.front().data<<' ';
    }
    cout<<endl;
    return 0;
}
/*
8 3
1 3 -1 -3 5 3 6 7
*/