ACM-単調行列のSliding Window——poj 2823
Sliding Window
Time Limit: 12000 MS
メモリLimit: 65536 K
Total Submissions: 36326
Acceepted: 10762
Case Time Limit: 5000 MS
Description
An array of size
n ≦10
6 is given to you.The e e e is a siding window of size
k which is moving from the very left of the array to the very right.You can only see the
k numbers in the window.Each time the sland window moves rightwards by one position.Following is an example:
The array is
[1] 3 -1 -3 5 3 6 7],and
k is 3.
Window position
Minimum value
Maximum 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
Your task is to determine the maximm and minimum values in the sland window at each position.
Input
The input consists of two lines.The first line contains two integers
n and
k which are the lengths of the array and the slaiding window.The re are
n integers in the second line.
Output
The re are two lines in the output.The first line gives the minimum values in the window at each position、from left to right、respively.The second line gives the maximvalues.
Sample Input
Time Limit: 12000 MS
メモリLimit: 65536 K
Total Submissions: 36326
Acceepted: 10762
Case Time Limit: 5000 MS
Description
An array of size
n ≦10
6 is given to you.The e e e is a siding window of size
k which is moving from the very left of the array to the very right.You can only see the
k numbers in the window.Each time the sland window moves rightwards by one position.Following is an example:
The array is
[1] 3 -1 -3 5 3 6 7],and
k is 3.
Window position
Minimum value
Maximum 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
Your task is to determine the maximm and minimum values in the sland window at each position.
Input
The input consists of two lines.The first line contains two integers
n and
k which are the lengths of the array and the slaiding window.The re are
n integers in the second line.
Output
The re are two lines in the output.The first line gives the minimum values in the window at each position、from left to right、respively.The second line gives the maximvalues.
Sample Input
8 3
1 3 -1 -3 5 3 6 7
-1 -3 -3 -3 3 3
3 3 5 5 6 7：http://poj.org/problem?id=2823hdu ， O(1) ， 。 ~① O(1) ？O(1) ， ， 。， 。， ？， / O（1） 。（ ） ： ， 。， STL ， ， 。， ， 。②：1、列の長さが一定であれば、最初の要素が規定範囲内にあるかどうかを判断し、もし範囲を超えたら、チームの首を長くする.
2、要素を加えるたびに、列の最後と比較し、現在の要素が列の最後より小さく、列が空でない場合は、尾のポインタを減少させ、列の調整を満たすまで、列の最後の要素が順次に列から出ます.
特に頭の針と尾の針の応用に注意します.
参考資料:http://www.cnblogs.com/neverforget/archive/2011/10/13/ll.html
http://xuyemin520.is-programmer.com/posts/25964
Andという問題は解決できます./************************************** *************************************** * Author:Tree * *From :http://blog.csdn.net/lttree * * Title : Sliding Window * *Source: poj 2823 * * Hint : * *************************************** **************************************/ #include#define MAX 1000001 int n,k; int pre1,pre2,lst1,lst2,len_max,len_min; // , ， int num[MAX],Increase[MAX],Decrease[MAX],Max[MAX],Min[MAX]; // Num ， ， ， 。 // void in_max(int i) { while( pre1<=lst1 && num[ Increase[lst1] ] =k ) { if(Increase[pre1]<=i-k) pre1++; Max[len_max++]=num[ Increase[pre1] ]; } } // void in_min(int i) { while( pre2<=lst2 && num[ Decrease[lst2] ]>num[i] ) --lst2; Decrease[++lst2]=i; // k ， if( i>=k ) { if(Decrease[pre2]<=i-k) pre2++; Min[len_min++]=num[ Decrease[pre2] ]; } } int main() { int i; while( ~scanf("%d%d",&n,&k) ) { // pre1=pre2=len_max=len_min=0; lst1=lst2=-1; // for(i=1;i<=n;++i) { scanf("%d",&num[i]); in_max(i); in_min(i); } // for( i=0;i