窗口（codevs 4373）

题目描述 Description

给你一个长度为N的数组，一个长为K的滑动的窗体从最左移至最右端，你只能见到窗口的K个数，每次窗体向右移动一位，如下表：

Window position	Min value	Max value
[ 1 3 -1 ] -3 5 3 6 7	-1	3
1 [ 3 -1 -3 ] 5 3 6 7	-3	3
1 3 [ -1 -3 5 ] 3 6 7	-3	5
1 3 -1 [ -3 5 3 ] 6 7	-3	5
1 3 -1 -3 [ 5 3 6 ] 7	3	6
1 3 -1 -3 5 [ 3 6 7 ]	3	7

你的任务是找出窗口在各位置时的max value, min value.

输入描述 Input Description

第1行n,k,第2行为长度为n的数组

输出描述 Output Description

2行

第1行每个位置的min value

第2行每个位置的max value

样例输入 Sample Input

8 3

1 3 -1 -3 5 3 6 7

样例输出 Sample Output

-1 -3 -3 -3 3 3

3 3 5 5 6 7

数据范围及提示 Data Size & Hint

数据范围：20%： n<=500; 50%: n<=100000;100%: n<=1000000;

/*

  单调队列

*/

#include<cstring>

#include<iostream>

#include<cstdio>

#define M 1000010

using namespace std;

int a[M],q[M],n,k,cnt;

int main()

{

    scanf("%d%d",&n,&k);

    for(int i=;i<=n;i++)

      scanf("%d",&a[i]);

    int head=,tail=;

    q[]=;

    for(int i=;i<=n;i++)

    {

        while(head<=tail&&q[head]+k<=i)head++;

        while(head<=tail&&a[q[tail]]>a[i])tail--;

        q[++tail]=i;

        if(i>=k)printf("%d ",a[q[head]]);

    }

    printf("\n");

    memset(q,,sizeof(q));

    head=,tail=;

    q[]=;

    for(int i=;i<=n;i++)

    {

        while(head<=tail&&q[head]+k<=i)head++;

        while(head<=tail&&a[q[tail]]<a[i])tail--;

        q[++tail]=i;

        if(i>=k)printf("%d ",a[q[head]]);

    }

    return ;

}

巴特西

窗口（codevs 4373）

最新文章

热门文章