POJ2823：Sliding Window

传送门

题意

有一个数列a，要求你求数列b和c，b[i]是a[i]…a[i+w-1]中的最小值，c[i]是最大值。如果a是1,3,-1,-3,5,3,6,7，则b为-1,-3,-3,-3,3,3，c为3,3,5,5,6,7。

分析

单调队列裸题，不过第一次写单调队列发现了很多trick

代码

#include <bits/stdc++.h>

using namespace std;

#define ll long long

#define F(i,a,b) for(int i=a;i<=b;++i)

#define R(i,a,b) for(int i=a;i<b;++i)

#define mem(a,b) memset(a,b,sizeof(a))

#pragma comment(linker, "/STACK:102400000,102400000")

inline void read(int &x){x=0; char ch=getchar();while(ch<'0') ch=getchar();while(ch>='0'){x=x*10+ch-48; ch=getchar();}}

int a[1001000],n,k,l,r,b[1001000];

pair<int,int>q[1001000];//1

int main()

{

    //freopen("data.in","r",stdin);

    //freopen("wa.out","w",stdout);

    while(scanf("%d %d",&n,&k)==2)

    {

        R(i,0,n) scanf("%d",a+i);

        l=r=0;

        q[r++]=make_pair(0,a[0]);

        R(i,1,k)

        {

            while(r&&a[i]<=q[r-1].second) r--;//2

            q[r++]=make_pair(i,a[i]);

        }

        b[1]=q[l].second;

        R(i,k,n)

        {

            while(r&&a[i]<=q[r-1].second) r--;

            l=min(l,r);//3

            q[r++]=make_pair(i,a[i]);

            while(i-k>q[l].first-1) l++;//4

            //printf("l=%d r=%d\n",l,r);

            b[i-k+2]=q[l].second;

        }

       // R(i,0,r) printf("%d%c",q[i].second,i==r-1?'\n':' ');

        F(i,1,n-k+1) printf("%d%c",b[i],i==n-k+1?'\n':' ');

        l=r=0;

        q[r++]=make_pair(0,a[0]);

        R(i,1,k)

        {

            while(r&&a[i]>=q[r-1].second) r--;

            q[r++]=make_pair(i,a[i]);

        }

        b[1]=q[l].second;

        R(i,k,n)

        {

            while(r&&a[i]>=q[r-1].second) r--;

            l=min(l,r);

            q[r++]=make_pair(i,a[i]);

            while(i-k>q[l].first-1) l++;

           // printf("l=%d r=%d\n",l,r);

            b[i-k+2]=q[l].second;

        }

        F(i,1,n-k+1) printf("%d%c",b[i],i==n-k+1?'\n':' ');

    }

    return 0;

}

/*

1.用pair记录每个放入队列的数的下标和值

2.从后往前找插入的位置，顺便删除后面的元素

3.更新左端点l

4.如果左端点的下标小于区域左端点，更逊左端点

*/

巴特西

POJ2823：Sliding Window

传送门

题意

分析

代码

最新文章

热门文章