求助

Lolierl @ 2018-05-01 20:37:14

#include<iostream>
#include<cstring>
using namespace std;
const int MAX=2147483647;

struct h
{
    int x;
    int num;
};
int main()
{
    int n,k;
    cin>>n>>k;
    int a[n+1];

    for(int i=1;i<=n;i++)
        cin>>a[i];

    h b[k+1];
    int l=1,r=0;
    for(int i=1;i<=k;i++)b[i].x=MAX;

    for(int i=1;i<=k;i++)
    {
        while(r>=l&&b[r].x>=a[i]){b[r].x=MAX;r--;}
        r++;b[r].x=a[i];b[r].num=i;
        /*cout<<a[i]<<endl;
        for(int j=1;j<=k;j++)cout<<b[j].x<<' ';
        cout<<endl;*/
    }
    /*for(int j=1;j<=k;j++)cout<<b[j].x<<' ';
    cout<<endl;*/
    cout<<b[l].x<<' ';
    for(int i=k+1;i<=n;i++)
    {
        if(b[l].num<=i-k)l++;
        while(r>=l&&b[r].x>=a[i]){b[r].x=MAX;r--;}
        r++;b[r].x=a[i];b[r].num=i; 
        cout<<b[l].x<<' ';  
        /*for(int j=1;j<=k;j++)cout<<b[j].x<<' ';
        cout<<endl;*/
    }
    cout<<endl;

    l=1,r=0;
    for(int i=1;i<=k;i++)b[i].x=-MAX;

    for(int i=1;i<=k;i++)
    {
        while(r>=l&&b[r].x<=a[i]){b[r].x=-MAX;r--;}
        r++;b[r].x=a[i];b[r].num=i;
    }
    cout<<b[l].x<<' ';
    for(int i=k+1;i<=n;i++)
    {
        if(b[l].num<=i-k)l++;
        while(r>=l&&b[r].x<=a[i]){b[r].x=-MAX;r--;}
        r++;b[r].x=a[i];b[r].num=i; 
        cout<<b[l].x<<' ';  
    }
    return 0;
}

by decoqwq @ 2018-05-01 20:42:17

@Lolierl segment tree

by Lolierl @ 2018-05-01 20:45:51

@刘浩宇（寂）

可以不用啊

by つきみやあゆ @ 2018-05-01 20:48:01

@Lolierl 建议了解一下正宗的单调队列姿势

by yjxyjx @ 2018-05-01 21:20:13

@Lolierl

我刚才copy了你的代码，然后做了一些改动：

1. 把l指针和r指针初始值都赋值为1

2. 由于我开数组向来都比较大，所以顺手把a数组的大小和b数组的大小都开为n + 10

主题思路并没有什么问题。

以上

将改好的代码顺便贴一下吧：

#include<iostream>
#include<cstring>
using namespace std;
const int MAX=2147483647;

struct h
{
    int x;
    int num;
};
int main()
{
    int n,k;
    cin>>n>>k;
    int a[n+10];

    for(int i=1;i<=n;i++)
        cin>>a[i];

    h b[n + 10];
    int l=1,r=1;
    for(int i=1;i<=k;i++)b[i].x=MAX;

    for(int i=1;i<=k;i++)
    {
        while(r>=l&&b[r].x>=a[i]){b[r].x=MAX;r--;}
        r++;b[r].x=a[i];b[r].num=i;
        /*cout<<a[i]<<endl;
        for(int j=1;j<=k;j++)cout<<b[j].x<<' ';
        cout<<endl;*/
    }
    /*for(int j=1;j<=k;j++)cout<<b[j].x<<' ';
    cout<<endl;*/
    cout<<b[l].x<<' ';
    for(int i=k+1;i<=n;i++)
    {
        if(b[l].num<=i-k)l++;
        while(r>=l&&b[r].x>=a[i]){b[r].x=MAX;r--;}
        r++;b[r].x=a[i];b[r].num=i; 
        cout<<b[l].x<<' ';  
        /*for(int j=1;j<=k;j++)cout<<b[j].x<<' ';
        cout<<endl;*/
    }
    cout<<endl;

    l=1,r=1;
    for(int i=1;i<=k;i++)b[i].x=-MAX;

    for(int i=1;i<=k;i++)
    {
        while(r>=l&&b[r].x<=a[i]){b[r].x=-MAX;r--;}
        r++;b[r].x=a[i];b[r].num=i;
    }
    cout<<b[l].x<<' ';
    for(int i=k+1;i<=n;i++)
    {
        if(b[l].num<=i-k)l++;
        while(r>=l&&b[r].x<=a[i]){b[r].x=-MAX;r--;}
        r++;b[r].x=a[i];b[r].num=i; 
        cout<<b[l].x<<' ';  
    }
    return 0;
}

题外话：

虽然不开氧气优化这份代码跑得挺快，但是在氧气优化的环境下，还是STL的双端队列快

所以安利一发我写的双端队列的博客求点赞

by Lolierl @ 2018-05-04 17:22:40

@yjxyjx

谢大佬