首页 > 其他 > 详细

UOJ #47.滑行的窗口

时间:2019-07-16 13:13:18      阅读:55      评论:0      收藏:0      [点我收藏+]

【题目描述】:

给定一个长度为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类型

需要读入输出优化

本题直接用两个单调队列维护长度为m的区间即可。

Code:
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<ctime>
#include<map>
#include<vector>
#include<set>
#include<queue>
#include<algorithm>
using namespace std;
const int N=1000005;
int n,m,a[N];
struct Node{
    int identity,value;
}Q[N];
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    int head=1,tail=0;
    for(int i=1;i<=n;i++){
        while(head<=tail&&i-Q[head].identity>=m){
            head++;
        }
        while(head<=tail&&a[i]<Q[tail].value){
            tail--;
        }
        Q[++tail].value=a[i];
        Q[tail].identity=i;
        if(i>=m){
            printf("%d ",Q[head].value);
        }
    }
    printf("\n");
    head=1,tail=0;
    for(int i=1;i<=n;i++){
        while(head<=tail&&i-Q[head].identity>=m){
            head++;
        }
        while(head<=tail&&a[i]>Q[tail].value){
            tail--;
        }
        Q[++tail].value=a[i];
        Q[tail].identity=i;
        if(i>=m){
            printf("%d ",Q[head].value);
        }
    }
    printf("\n");
    return 0;
}

UOJ #47.滑行的窗口

原文:https://www.cnblogs.com/ukcxrtjr/p/11194131.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!