POJ 2823 UESTCoj 1221 Sliding Window 单调队列 经典入门题
题意：给出一个序列，求出每连续k个数字中最大的数和最小的数。
这是道单调队列裸题，直接写就行了。
本来用deque写出来后，发现在poj上硬是超时了，在discuss上看很多人也在抱怨超时的问题，据说在uestc上也有这题，我过去提交终于过了。。。
但是poj还是没有过，于是我用数组模拟队列来写，提交还是超时，折腾了一会，把g++改成c++终于5s多过了。。。
注意如果是直接输出答案的话，如果k=1可能会出错。
代码：
#include <cstdio>#include <cstring>#include <deque>using namespace std;const int MAXN = 1000005;int n, k, t, arr[MAXN], que[MAXN];void solve(bool flag) {int head(0), rear(0);memset(que, 0, sizeof(que));if (k == 1) printf("%d ", arr[0]);for (int i = 1; i < n; i++) {if (flag) while (head <= rear && arr[i] > arr[que[rear]])rear--;else while (head <= rear && arr[i] < arr[que[rear]])rear--;que[++rear] = i;if (que[head] < i - k + 1) head++;if (i >= k - 1)if (i == n - 1) printf("%d\n", arr[que[head]]);else printf("%d ", arr[que[head]]);}}int main() {while (scanf("%d%d", &n, &k) != EOF) {for (int i = 0; i < n; i++)scanf("%d", &arr[i]);solve(0);solve(1);}return 0;}