题解 P1886 【滑动窗口】

Porsche · 2019-01-28 17:01:59 · 题解

首先这道题考虑计算出当前窗口内的最长上升（下降）序列，并存储起来，每次输出队列最前面的值。 上代码↓

#include<bits/stdc++.h>//万能大法好，三岁保平安~
using namespace std;
struct rec
{
    int s;
    int d;
}e[10000001];//结构体e存储当前队列中点的值s和编号d 
int a[10000001];//存储这一堆数字 
int head=1,tail=1;//head存储当前队列头的编号，tail存储当前队列尾的编号 
bool flag;
int main()
{
    int n,k;
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    //计算当前窗口内的最小值 
    e[1].s=a[1];//先把第一个数添进去 
    for(int i=2;i<=k;i++)//计算窗口在最前端的时候队列里的情况 
    {
        flag=0;
        for(int j=head;j<=tail;j++)
        {
            if(e[j].s>a[i])//如果当前a[i]比当前队列里这一位小则优先利用a[i]，替换队列中的当前位 
            {
                e[j].s=a[i];
                e[j].d=i;
                tail=j;
                flag=1;
            }
        }
        if(!flag)//如果没有出现这种情况，即a[i]比当前队列里的所有书都大 
        {
            e[++tail].s=a[i];
            e[tail].d=i;
        }
    }
    cout<<e[head].s<<' ';
    for(int i=k+1;i<=n;i++)//枚举以后的点，区别在于要考虑窗口的头 
    {
        flag=0;
        for(int j=head;j<=tail;j++)
        {
            if(e[j].d<i-k+1)//如果哦当前队列里的当前点已经不在窗口里了，就去掉这个点 
            {
                head++;
                continue;
            }
            if(e[j].s>a[i])
            {
                e[j].s=a[i];
                e[j].d=i;
                tail=j;
                flag=1;
            }
        }
        if(!flag)
        {
            e[++tail].s=a[i];
            e[tail].d=i;
        }
        cout<<e[head].s<<' ';
    }
    cout<<endl;
    head=tail=1;//注意head和tail需要归为1 
    for(int i=1;i<=2*n;i++)e[i].s=e[i].d=0;//队列初始化 
    //求取最大值的时候与求取最小值的时候同理，注意队列是下降序列即可 
    e[1].s=a[1];
    for(int i=2;i<=k;i++)
    {
        flag=0;
        for(int j=head;j<=tail;j++)
        {
            if(e[j].s<a[i])
            {
                e[j].s=a[i];
                e[j].d=i;
                tail=j;
                flag=1;
            }
        }
        if(!flag)
        {
            e[++tail].s=a[i];
            e[tail].d=i;
        }
    }
    cout<<e[head].s<<' ';
    for(int i=k+1;i<=n;i++)
    {
        flag=0;
        for(int j=head;j<=tail;j++)
        {
            if(e[j].d<i-k+1)
            {
                head++;
                continue;
            }
            if(e[j].s<a[i])
            {
                e[j].s=a[i];
                e[j].d=i;
                tail=j;
                flag=1;
            }
        }
        if(!flag)
        {
            e[++tail].s=a[i];
            e[tail].d=i;
        }
        cout<<e[head].s<<' ';
    }
    return 0;
}

有不理解的可以私信我