队列型DP【仅题目】

Window

(window时限2s;256M)

给你一个长度为N的数组,一个长为K的滑动的窗体从最左移至最右端,你只能见到窗口的K个数,每次窗体向右移动一位,如下表:

Window position Min value Max value
[ 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

 

你的任务是找出窗口在各位置时的max value,min value.

输入格式:

第1行n,k,第2行为长度为n的数组

输出格式:

2行,第1行每个位置的min value,第2行每个位置的max value

样例:

window.in

8 3

1 3 -1 -3 5 3 6 7

window.out

-1 -3 -3 -3 3 3

3 3 5 5 6 7

数据范围:

20%: n<=500; 50%: n<=100000;

100%: n<=1000000;

 

 

 

 

页面: 1 2

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注