【NOIP模拟赛】滑动的窗户

2014年11月4日1,5200

【题目描述】

在一个包含n个元素的数组上,有一个长度为k的窗户在从左向右滑动。窗户每滑动到一个位置,我们都可以看到k个元素在窗户中。如下的例子所示,假设数组为 [1 3 -1 -3 5 3 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

对于窗户滑动过的每个位置,请给出窗户内k个元素的最小值和最大值。

【输入】

输入文件:window.in

输入的第一行包括两个整数n,k,n表示数组的长度,k表示窗户的长度。

接下来一行包括n个整数,表示这个n个元素的数组。

【输出】

输出文件:window.out

输出包含两行,每行包括n-k+1个整数,第一行表示窗户从左到右滑动过程中的最小值,第二行表示窗户从左到右滑动过程中的最大值。

【输入样例】

8 3

1 3 -1 -3 5 3 6 7

【输出样例】

-1 -3 -3 -3 3 3

3 3 5 5 6 7

【数据范围】

  对于100%的数据,3<=n<=1000000,1<=k<=n,数组中的每个元素均在int范围内

题解

这个经典的单调队列吧,娱乐的话堆也是可以的