WHYZOJ-#47. 滑行的窗口(单调队列)_weixin_34378922的博客-程序员宅基地

【题目描述】:

给定一个长度为n的数列a,再给定一个长度为k的滑动窗口,从第一个数字开始依次框定k个数字,求每次框定的数字中的最大值和最小值,依次输出所有的这些值。下面有一个例子数组是 [1 3 1 3 5 6 7] , k 是3:

       窗口位置              窗口中的最小值   窗口中的最大值
[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

【输入描述】:

第一行包含两个整数 n 和 k ,分别表示数组的长度和滑动窗口长度。

第二行n个整数,表示数列元素的值。

【输出描述】:

第一行从左到右窗口看到的最小值。

第二行从左到右窗口看到的最大值。

【样例输入】:

8 3
1 3 -1 -3 5 3 6 7

【样例输出】:

-1 -3 -3 -3 3 3
3 3 5 5 6 7

【时间限制、数据范围及描述】:

时间:1s 空间:64M

30%:n<=100 k<=20

60%:n<=5000 k<=20

100%:n<=10^6,每个元素不操过int类型

需要读入输出优化

二十分钟敲完……手速还算可以:( 不过今天也就这样了;(

 1 #include "bits/stdc++.h"
 2 using namespace std;
 3 typedef long long LL;
 4 const int MAX=1000005;
 5 int n,m;
 6 int a[MAX];
 7 struct Que{
 8     int na;
 9     int sco;
10 }q[MAX];
11 inline int read(){
12     int an=0,x=1;char c=getchar();
13     while (c<'0' || c>'9') {
    if (c=='-') x=-1;c=getchar();}
14     while (c>='0' && c<='9') {an=an*10+c-'0';c=getchar();}
15     return an*x;
16 }
17 void getmin(){
18     int i,j;
19     int head=1,tail=0;
20     for (i=1;i<=n;i++){
21         while (head<=tail && i-q[head].na>=m) head++;
22         while (head<=tail && a[i]<q[tail].sco) tail--;
23         q[++tail].sco=a[i];q[tail].na=i;
24         if (i>=m){
25             printf("%d ",q[head].sco);
26         }
27     }
28     printf("\n");
29 }
30 void getmax(){
31     int i,j;
32     int head=1,tail=0;
33     for (i=1;i<=n;i++){
34         while (head<=tail && i-q[head].na>=m) head++;
35         while (head<=tail && a[i]>q[tail].sco) tail--;
36         q[++tail].sco=a[i];q[tail].na=i;
37         if (i>=m){
38             printf("%d ",q[head].sco);
39         }
40     }
41     printf("\n");
42 }
43 int main(){
44     freopen ("window.in","r",stdin);
45     freopen ("window.out","w",stdout);
46     int i,j;
47     n=read();m=read();
48     for (i=1;i<=n;i++){
49         a[i]=read();
50     }
51     getmin();
52     getmax();
53     return 0;
54 }

 

转载于:https://www.cnblogs.com/keximeiruguo/p/7555058.html

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/weixin_34378922/article/details/94706529

智能推荐

随便推点