POJ2823 http://poj.org/problem?id=2823
最基础的单调队列，说是数据结构，其实就是一种更新数组数据的方法。
之前还准备用deque，超时了，直接head,tail快得多。
一直把删除队首过期元素写在删除队尾之前，就一直WA，尼玛换一下顺序就好了。
#include <iostream>
#include <cstdio>
#include <cstring>
//#define OPEN_FILE
using namespace std;
const int MAXN = ;
int n, w;
struct Node{
int v, p;
}a[MAXN], d[MAXN];
inline bool cmp(int a, int b){
if (a < b) return true;
if (a > b) return false;
return false;
}
void work(bool flag)
{
int i, head, tail;
memset(d, , sizeof(d));
head = tail = ;
d[head] = a[];
for (i = ; i <= w; i++){
while (cmp(d[tail].v, a[i].v) == flag){
tail--;
if (tail < head) break;
}
d[++tail] = a[i];
}
printf("%d", d[head]);
for (i = w + ; i <= n; i++){
if (head <= tail){
while (cmp(d[tail].v, a[i].v) == flag){
tail--;
if (head > tail) break;
}
}
d[++tail] = a[i];
while (d[head].p <= i - w){
head++;
}
printf(" %d", d[head]);
}
} int main()
{
#ifdef OPEN_FILE
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#endif // OPEN_FILE
int i;
scanf("%d%d", &n, &w);
for (i = ; i <= n; i++){
scanf("%d", &a[i].v);
a[i].p = i;
}
work(false);
printf("\n");
work(true);
printf("\n");
}