洛谷 P2032 扫描

P2032 扫描

题目描述

有一个 1 ∗ n 的矩阵，有 n 个正整数。

现在给你一个可以盖住连续的 k 的数的木板。

一开始木板盖住了矩阵的第 1 ∼ k 个数，每次将木板向右移动一个单位，直到右端与

第 n 个数重合。

每次移动前输出被覆盖住的最大的数是多少。

输入输出格式

输入格式：

 

第一行两个数，n，k，表示共有 n 个数，木板可以盖住 k 个数。

第二行 n 个数，表示矩阵中的元素。

 

输出格式：

 

共 n − k + 1 行，每行一个正整数。

第 i 行表示第 i ∼ i + k − 1 个数中最大值是多少。

 

输入输出样例

输入样例#1： 复制

5 3
1 5 3 4 2

输出样例#1： 复制

5
5
4

说明

对于 20% 的数据保证：1 ≤ n ≤ 1e3，1 ≤ k ≤ n

对于 50% 的数据保证：1 ≤ n ≤ 1e4，1 ≤ k ≤ n

对于 100% 的数据保证：1 ≤ n ≤ 2 ∗ 1e6，1 ≤ k ≤ n

矩阵中元素大小不超过 1e4。

注意符号是换行符。

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int n,k,l,r;
int a[1000010],b[100010];
int main(){
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++)    scanf("%d",&a[i]);
    for(int i=1;i<=n;i++){
        while(l<=r&&b[l]<=i-k)    l++;
        while(l<=r&&a[i]>a[b[r]])    r--;
        b[++r]=i;
        if(i>=k)    printf("%d
",a[b[l]]);
    }
}