UOJ #47.滑行的窗口-白红宇

UOJ #47.滑行的窗口

阅读量：4500 次

发布时间：2019-06-08

本文共 1588 字，大约阅读时间需要 5 分钟。

【题目描述】：给定一个长度为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 31 3 -1 -3 5 3 6 7【样例输出】：-1 -3 -3 -3 3 33 3 5 5 6 7【时间限制、数据范围及描述】：时间：1s 空间：64M30%：n<=100 k<=2060%：n<=5000 k<=20100%：n<=10^6，每个元素不操过int类型需要读入输出优化本题直接用两个单调队列维护长度为m的区间即可。Code:#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          #include
           
            #include
            
             #include
             
              #include
              
               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]
               
                =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;}