FZU1894
1346 ワード
标题:キュー問題、Cはインキュー、Qは出力キューのRPの最大値、Gは削除キューヘッダの要素
構想:他人の構想を見て、配列で単調なキューをシミュレートする
構想:他人の構想を見て、配列で単調なキューをシミュレートする
#include <stdio.h>
#include <string.h>
#define MAXN 1000100
typedef struct {
int value;
int num;
}QUEUE;
QUEUE queue[MAXN];
int main() {
int T;
char name[10];
char s[20];
scanf("%d",&T);
while (T--) {
scanf("%s", s);
int front = 1; //
int cnt = 0; //
int head = 1; //
int rear = 0; //
int rp;
while (scanf("%s",s) != EOF) {
if (!strcmp(s,"END"))
break;
if (strcmp(s, "C") == 0) {
scanf("%s%d", name, &rp);
while (head <= rear && rp > queue[rear].value)
rear--;
queue[++rear].value = rp;
queue[rear].num = ++cnt;
}
else if (strcmp(s, "G") == 0) {
while (head <= rear && queue[head].num <= front) //
head++;
front++;
}
else if (strcmp(s, "Q") == 0)
printf("%d
",head > rear ? -1 : queue[head].value);
}
}
return 0;
}