http://acm.fzu.edu.cn/problem.php?pid=1894志愿者选拔 O(n)
最最入门的单调队列,而且是很形象的排队问题
#include <stdio.h>
#include <string.h>
const int N = 1000005;
int que[N][2], v;
char op[10];
int tail, head, id, now;
inline void push(int v, int id) {
while( tail >= head && que[tail][0]<v) tail--;
que[++tail][0] = v;
que[tail][1] = id;
}
inline void pop() {
if( tail >= head && que[head][1] == now) head ++;
now ++;
}
inline void out() {
if( tail < head ) puts("-1");
else printf("%d\n", que[head][0]);
}
int main() {
int t;
scanf("%d", &t);
while( t --) {
head = 0, tail = -1; id = 0, now = 0;
while( scanf("%s", op)!= EOF )
if ( !strcmp(op, "START") ) break;
while( scanf("%s", op) ) {
if( !strcmp(op, "END") ) break;
if( op[0] == 'C' ) {
scanf("%s", op);
scanf("%d", &v);
push(v, id);
id ++;
} else if( op[0] == 'G' ) {
pop();
} else if( op[0] == 'Q' ) {
out();
}
}
}
}
Sliding Window O(n)
同上题
http://acm.pku.edu.cn/JudgeOnline/problem?id=2823
#include <stdio.h>
#include <string.h>
const int N = 1000005;
int n, k;
struct node {
int num, id;
} min[N], max[N];
int minans[N], maxans[N], x;
int head[2], tail[2], cnt = 0;
int main() {
while( scanf("%d %d", &n, &k) != EOF ) {
head[0] = head[1] = -1;
tail[0] = tail[1] = 0;
cnt = 0;
for(int i = 0; i < n; i ++) {
scanf("%d", &x);
while( head[0] >= tail[0] && min[tail[0]].id + k - 1 < i ) tail[0]++;
while( head[1] >= tail[1] && max[tail[1]].id + k - 1 < i ) tail[1]++;
while( head[0] >= tail[0] && min[head[0]].num >= x) head[0] --;
min[++head[0]].num = x;
min[head[0]].id = i;
while( head[1] >= tail[1] && max[head[1]].num <= x) head[1] --;
max[++head[1]].num = x;
max[head[1]].id = i;
if( i >= k - 1 ){
minans[cnt] = min[tail[0]].num;
maxans[cnt] = max[tail[1]].num;
cnt ++;
}
}
for(int i = 0; i < cnt; i ++)
if(i == 0) printf("%d", minans[i]);
else printf(" %d", minans[i]);
puts("");
for(int i = 0; i < cnt; i ++)
if(i == 0) printf("%d", maxans[i]);
else printf(" %d", maxans[i]);
puts("");
}
}
1