poj 2823 Sliding Window

解题思路：单调队列或 RMQ

  1 //解题方法：单调队列
  2 
  3 ///////////////////////////////////////////////////////////////////////////
  4 //problem_id: poj 2823
  5 //user_id: SCNU20102200088
  6 ///////////////////////////////////////////////////////////////////////////
  7 
  8 #include <algorithm>
  9 #include <iostream>
 10 #include <iterator>
 11 #include <iomanip>
 12 #include <cstring>
 13 #include <cstdlib>
 14 #include <string>
 15 #include <vector>
 16 #include <cstdio>
 17 #include <cctype>
 18 #include <cmath>
 19 #include <queue>
 20 #include <stack>
 21 #include <list>
 22 #include <set>
 23 #include <map>
 24 using namespace std;
 25 
 26 ///////////////////////////////////////////////////////////////////////////
 27 typedef long long LL;
 28 const double PI=acos(-1.0);
 29 ///////////////////////////////////////////////////////////////////////////
 30 
 31 ///////////////////////////////////////////////////////////////////////////
 32 //Add Code:
 33 int MIN[1000005],MAX[1000005];
 34 
 35 struct Node{
 36     int key,tag;
 37     Node(int k=0,int t=0):key(k),tag(t){}
 38 }Min[1000005],Max[1000005];
 39 
 40 inline int Scanf(){
 41     int val=0,sgm=1;
 42     char c;
 43     while(true){
 44         c=getchar();
 45         if(c=='
' || c==' '){
 46             val=val*sgm;
 47             break;
 48         }
 49         if(c=='-') sgm=-1;
 50         if(c>='0' && c<='9') val=val*10+c-48;
 51     }
 52     return val;
 53 }
 54 
 55 inline void Print(int x){
 56     if(x<0){
 57         putchar('-');
 58         x=-x;
 59     }
 60     if(x==0){
 61         putchar('0');
 62         return;
 63     }
 64     char s[20];
 65     int len=0;
 66     while(x){
 67         s[len++]=x%10+'0';
 68         x/=10;
 69     }
 70     while(len--) putchar(s[len]);
 71     return;
 72 }
 73 ///////////////////////////////////////////////////////////////////////////
 74 
 75 int main(){
 76     ///////////////////////////////////////////////////////////////////////
 77     //Add code:
 78     int n,k,val,i;
 79     int Min_tail=0,Min_head=1;
 80     int Max_tail=0,Max_head=1;
 81     //scanf("%d%d",&n,&k);
 82     n=Scanf(),k=Scanf();
 83     for(i=1;i<=k;i++){
 84         //scanf("%d",&val);
 85         val=Scanf();
 86         while(Min_tail>=Min_head && Min[Min_tail].key>=val) Min_tail--;
 87         Min[++Min_tail]=Node(val,i);
 88         while(Max_tail>=Max_head && Max[Max_tail].key<=val) Max_tail--;
 89         Max[++Max_tail]=Node(val,i);
 90     }
 91     int id=1;
 92     MIN[id]=Min[Min_head].key,MAX[id]=Max[Max_head].key;
 93     for(i=k+1;i<=n;i++){
 94         //scanf("%d",&val);
 95         val=Scanf();
 96         while(Min_tail>=Min_head && Min[Min_tail].key>=val) Min_tail--;
 97         Min[++Min_tail]=Node(val,i);
 98         while(Max_tail>=Max_head && Max[Max_tail].key<=val) Max_tail--;
 99         Max[++Max_tail]=Node(val,i);
100         if(Min[Min_head].tag==id) Min_head++;
101         if(Max[Max_head].tag==id) Max_head++;
102         id++;
103         MIN[id]=Min[Min_head].key,MAX[id]=Max[Max_head].key;
104     }
105     for(i=1;i<id;i++){
106         //printf("%d ",MIN[i]);
107         Print(MIN[i]);
108         putchar(' ');
109     }
110     //printf("%d
",MIN[id]);
111     Print(MIN[id]);
112     putchar('
');
113     for(i=1;i<id;i++){
114         //printf("%d ",MAX[i]);
115         Print(MAX[i]);
116         putchar(' ');
117     }
118     //printf("%d
",MAX[id]);
119     Print(MAX[id]);
120     putchar('
');
121     ///////////////////////////////////////////////////////////////////////
122     return 0;
123 }
124 
125 ///////////////////////////////////////////////////////////////////////////
126 /*
127 Testcase:
128 Input:
129 8 3
130 1 3 -1 -3 5 3 6 7
131 Output:
132 -1 -3 -3 -3 3 3
133 3 3 5 5 6 7
134 */
135 ///////////////////////////////////////////////////////////////////////////

  1 //解题方法：RMQ
  2 
  3 ///////////////////////////////////////////////////////////////////////////
  4 //problem_id: poj 2823
  5 //user_id: SCNU20102200088
  6 ///////////////////////////////////////////////////////////////////////////
  7 
  8 #include <algorithm>
  9 #include <iostream>
 10 #include <iterator>
 11 #include <iomanip>
 12 #include <cstring>
 13 #include <cstdlib>
 14 #include <string>
 15 #include <vector>
 16 #include <cstdio>
 17 #include <cctype>
 18 #include <cmath>
 19 #include <queue>
 20 #include <stack>
 21 #include <list>
 22 #include <set>
 23 #include <map>
 24 using namespace std;
 25 
 26 ///////////////////////////////////////////////////////////////////////////
 27 typedef long long LL;
 28 const double PI=acos(-1.0);
 29 ///////////////////////////////////////////////////////////////////////////
 30 
 31 ///////////////////////////////////////////////////////////////////////////
 32 //Add Code:
 33 int a[1000005],Min[1000005],Max[1000005];
 34 
 35 int min(int a,int b){
 36     return a<b? a:b;
 37 }
 38 
 39 int max(int a,int b){
 40     return a>b? a:b;
 41 }
 42 
 43 void RMQ(int n,int k,int t){
 44     int i,j;
 45     for(i=1;i<=n;i++) Max[i]=Min[i]=a[i];
 46     for(i=1;i<=t;i++){
 47         for(j=1;j+(1<<i)-1<=n;j++){
 48             Min[j]=min(Min[j],Min[j+(1<<(i-1))]);
 49             Max[j]=max(Max[j],Max[j+(1<<(i-1))]);
 50         }
 51     }
 52 }
 53 
 54 inline int Scanf(){
 55     int val=0,sgm=1;
 56     char c;
 57     while(true){
 58         c=getchar();
 59         if(c=='
' || c==' '){
 60             val=val*sgm;
 61             break;
 62         }
 63         if(c=='-') sgm=-1;
 64         if(c>='0' && c<='9') val=val*10+c-48;
 65     }
 66     return val;
 67 }
 68 
 69 inline void Print(int x){
 70     if(x<0){
 71         putchar('-');
 72         x=-x;
 73     }
 74     if(x==0){
 75         putchar('0');
 76         return;
 77     }
 78     char s[20];
 79     int len=0;
 80     while(x){
 81         s[len++]=x%10+'0';
 82         x/=10;
 83     }
 84     while(len--) putchar(s[len]);
 85     return;
 86 }
 87 ///////////////////////////////////////////////////////////////////////////
 88 
 89 int main(){
 90     ///////////////////////////////////////////////////////////////////////
 91     //Add code:
 92     int n,k,i,t=0;
 93     //scanf("%d%d",&n,&k);
 94     n=Scanf(),k=Scanf();
 95     for(i=1;i<=n;i++){
 96         //scanf("%d",&a[i]);
 97         a[i]=Scanf();
 98     }
 99     while((1<<(t+1))<=k) t++;  //求满足2^t<=k的最大的t
100     RMQ(n,k,t);
101     for(i=1;i<=n-k+1;i++){
102         //printf("%d",min(Min[i],Min[i+k-(1<<t)]));
103         Print(min(Min[i],Min[i+k-(1<<t)]));
104         //if(i<n-k+1) printf(" ");
105         if(i<n-k+1) putchar(' ');
106         //else printf("
");
107         else putchar('
');
108     }
109     for(i=1;i<=n-k+1;i++){
110         //printf("%d",max(Max[i],Max[i+k-(1<<t)]));
111         Print(max(Max[i],Max[i+k-(1<<t)]));
112         //if(i<n-k+1) printf(" ");
113         if(i<n-k+1) putchar(' ');
114         //else printf("
");
115         else putchar('
');
116     }
117     ///////////////////////////////////////////////////////////////////////
118     return 0;
119 }
120 
121 ///////////////////////////////////////////////////////////////////////////
122 /*
123 Testcase:
124 Input:
125 8 3
126 1 3 -1 -3 5 3 6 7
127 Output:
128 -1 -3 -3 -3 3 3
129 3 3 5 5 6 7
130 */
131 ///////////////////////////////////////////////////////////////////////////