[poj2823]Sliding Window（单调队列）
标签：span namespace eof return 注意 iostream 否则 超时 style
题意：给定一个序列，求所有滑动窗口内的最值。
解题关键：单调队列裸题，单调递增队列选取最小值，单调递减队列选取最大值。
注意用c++提交，否则会超时。
1 #include 2 #include 3 #include
4 #include 5 #include 6 #include 7 #define maxn 1000005
8 using namespace std;
9 typedef long long ll;
10 int n,k;
11 int min1[maxn],max1[maxn],pos1[maxn],que1[maxn],a[maxn];
12 inline int read(){
13 char k=0;char ls;ls=getchar();for(;ls‘0‘||ls>‘9‘;k=ls,ls=getchar());
14 int x=0;for(;ls>=‘0‘&&ls‘9‘;ls=getchar())x=(x3)+(x1)+ls-‘0‘;
15 if(k==‘-‘)x=0-x;return x;
16 }
17 inline void get_min(int n,int k){
18 int head=0,rear=0;
19 for(int i=1;i){
20 while(rear>head&&que1[rear-1]>a[i]) rear--;
21 que1[rear]=a[i];
22 pos1[rear]=i;
23 rear++;
24 }
25 for(int i=k;i){
26 while(rear>head&&que1[rear-1]>a[i]) rear--;
27 que1[rear]=a[i];
28 pos1[rear]=i;
29 rear++;
30 while(pos1[head]1) head++;
31 min1[i]=que1[head];
32 }
33 }
34 inline void get_max(int n,int k){
35 int head=0,rear=0;
36 for(int i=1;i){
37 while(rear>head&&que1[rear-1];
38 que1[rear]=a[i];
39 pos1[rear]=i;
40 rear++;
41 }
42 for(int i=k;i){
43 while(rear>head&&que1[rear-1];
44 que1[rear]=a[i];
45 pos1[rear]=i;
46 rear++;
47 while(pos1[head]1) head++;
48 max1[i]=que1[head];
49 }
50 }
51 int main(){
52 while(scanf("%d%d",&n,&k)!=EOF){
53 for(int i=1;iread();
54 get_min(n,k);
55 get_max(n,k);
56 for(int i=k;i){
57 printf("%d%c",min1[i],i==n?‘\n‘:‘ ‘);
58 }
59 for(int i=k;i){
60 printf("%d%c",max1[i],i==n?‘\n‘:‘ ‘);
61 }
62 }
63 }
[poj2823]Sliding Window（单调队列）
标签：span namespace eof return 注意 iostream 否则 超时 style
原文地址：http://www.cnblogs.com/elpsycongroo/p/7639470.html
评论