poj 2823 Sliding Window

　　入门级的单调队列，不过我的代码要用cout加上poj的g++才能3500ms左右通过，不然就会超时了！

View Code

 1 #include <cstdio>
 2 #include <cstdlib>
 3 #include <cstring>
 4 #include <cmath>
 5 #include <iostream>
 6 
 7 using namespace std;
 8 
 9 const int maxn = 1000001;
10 
11 void scan(int &n){
12     char ch;
13 
14     while ((ch = getchar()) != '-' && ('0' > ch || ch > '9'));
15     if (ch != '-'){
16         n = ch - '0';
17         while ((ch = getchar()) >= '0' && ch <= '9')
18             n = n * 10 + ch - '0';
19     }
20     else{
21         n = 0;
22         while ((ch = getchar()) >= '0' && ch <= '9')
23             n = n * 10 + '0' - ch;
24     }
25 }
26 
27 int qmx[maxn], imx[maxn], qmxh, qmxt;
28 int qmn[maxn], imn[maxn], qmnh, qmnt;
29 int rec[maxn];
30 
31 int main(){
32     int n, k, a;
33 
34     scan(n);
35     scan(k);
36     qmxh = qmxt = qmnh = qmnt = 0;
37 
38     for (int i = 0; i < n; i++){
39         scan(a);
40         while (qmxh < qmxt && qmx[qmxt - 1] <= a) qmxt--;
41         qmx[qmxt] = a;
42         imx[qmxt++] = i;
43         while (qmnh < qmnt && qmn[qmnt - 1] >= a) qmnt--;
44         qmn[qmnt] = a;
45         imn[qmnt++] = i;
46 
47         if (i < k - 1) continue;
48         if (i - imx[qmxh] >= k) qmxh++;
49         if (i - imn[qmnh] >= k) qmnh++;
50         cout << qmn[qmnh] << ' ';
51         //printf("%d ", qmn[qmnh]);
52         rec[i] = qmx[qmxh];
53     }
54     puts("");
55     for (int i = k - 1; i < n; i++)
56         cout << rec[i] << ' ';
57         //printf("%d ", rec[i]);
58     puts("");
59 
60     return 0;
61 }

——written by Lyon