| Time Limit: 12000MS | Memory Limit: 65536K | |
| Total Submissions: 35486 | Accepted: 10492 | |
| Case Time Limit: 5000MS | ||
Description
| 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 maximum and minimum values in the sliding
window at each position.
Input
Output
Sample Input
8 3 1 3 -1 -3 5 3 6 7
Sample Output
-1 -3 -3 -3 3 3 3 3 5 5 6 7
PS:单调队列水体。
妈蛋poj还卡scanf，G++超时，换c++输入会快些
mycode1 #include<cstdio>
2 #include<cstring>
3 #include<algorithm>
4 using namespace std;
5 const int MAX = 1e6+10;
6 int a[MAX],b[MAX],pos1[MAX],pos2[MAX];
7 int ans1[MAX],ans2[MAX];
8 int main()
9 {
10 int x,n,k; int cur1,cur2;
11 scanf("%d %d",&n,&k);
12 int rear=0,front=0; cur1=cur2=0;
13 int rear2=0,front2=0;
14 for(int i=0;i<n;i++)
15 {
16 scanf("%d",&x);
17 while(front<rear&&a[rear-1]>x) rear--;
18 a[rear]=x; pos1[rear++]=i;
19 while(front2<rear2&&b[rear2-1]<x) rear2--;
20 b[rear2]=x; pos2[rear2++]=i;
21 if(i>=k-1)
22 {
23 ans1[cur1++]=a[front];
24 ans2[cur2++]=b[front2];
25 if(i-pos1[front]+1>=k) front++;
26 if(i-pos2[front2]+1>=k) front2++;
27 }
28 }
29 for(int i=0;i<cur1;i++)
30 {
31 if(i) printf(" %d",ans1[i]);
32 else printf("%d",ans1[i]);
33 }
34 printf("\n");
35 for(int i=0;i<cur2;i++)
36 {
37 if(i) printf(" %d",ans2[i]);
38 else printf("%d",ans2[i]);
39 }
40 printf("\n");
41
42 return 0;
43 }
POJ 2823 Sliding Window,布布扣,bubuko.com
原文：http://www.cnblogs.com/acvc/p/3601580.html
