2500 問(wèn)題 G: 信息學(xué)奧賽一本通T1597-滑動(dòng)窗口
時(shí)間限制: 1s
內(nèi)存限制: 128MB 提交: 359 解決: 78
題目描述
原題來(lái)自：POJ 2823
給一個(gè)長(zhǎng)度為 N 的數(shù)組，一個(gè)長(zhǎng)為 K 的滑動(dòng)窗體從最左端移至最右端，你只能看到窗口中的 K 個(gè)數(shù)，每次窗體向右移動(dòng)一位，如下圖：
你的任務(wù)是找出窗體在各個(gè)位置時(shí)的最大值和最小值。
輸入
第 1 行：兩個(gè)整數(shù) N 和 K；
第 2 行：N 個(gè)整數(shù)，表示數(shù)組的 N 個(gè)元素(≤2×109 )；
第 2 行：N 個(gè)整數(shù)，表示數(shù)組的 N 個(gè)元素(≤2×109 )；
輸出
第一行為滑動(dòng)窗口從左向右移動(dòng)到每個(gè)位置時(shí)的最小值，每個(gè)數(shù)之間用一個(gè)空格分開(kāi)；
第二行為滑動(dòng)窗口從左向右移動(dòng)到每個(gè)位置時(shí)的最大值，每個(gè)數(shù)之間用一個(gè)空格分開(kāi)。
第二行為滑動(dòng)窗口從左向右移動(dòng)到每個(gè)位置時(shí)的最大值，每個(gè)數(shù)之間用一個(gè)空格分開(kāi)。
樣例輸入
8 3 1 3 -1 -3 5 3 6 7
樣例輸出
-1 -3 -3 -3 3 3 3 3 5 5 6 7
提示
數(shù)據(jù)范圍與提示：
對(duì)于 20% 的數(shù)據(jù)，K≤N≤1000；
對(duì)于 50% 的數(shù)據(jù)，K≤N≤105 ；
對(duì)于 100% 的數(shù)據(jù)，K≤N≤106 。
對(duì)于 20% 的數(shù)據(jù)，K≤N≤1000；
對(duì)于 50% 的數(shù)據(jù)，K≤N≤105 ；
對(duì)于 100% 的數(shù)據(jù)，K≤N≤106 。
比賽公告
藍(lán)橋杯備賽系列訓(xùn)練賽
希望大家能夠認(rèn)真、堅(jiān)持、分享、討論，就能夠取得好的成績(jī)