训练赛的题……
暴力一波明显超时……
最近刚学stl 感觉是优先队列 但还是太会用……
以后可以试一下优先队列……
比赛之后百度了一下 发现是单调队列……
看起来挺简单的 也算个模版题吧……
总之思路就是维护一个单调队列……
有用的的只有C G Q……
那个长度最多是5的名字只用接着 根本没用……
直接上代码……
#include<stdio.h>
#include<iostream>
#include<string.h>
#include<algorithm>
#include<math.h>
using namespace std;
struct p{
int num,rp;
}people[];
int main(){
int T;
scanf("%d",&T);
while(T--){
char s[];
int head=,first=,tail=-,n=;
while(~scanf("%s",s)&&strcmp(s,"END")!=){
if(s[]=='C'){
char name[];
int val;
scanf("%s%d",name,&val);
while(tail>=head&&people[tail].rp<=val) tail--;
people[++tail].rp=val;
people[tail].num=n++;
}
else if(s[]=='Q'){
while(tail>=head&&people[head].num<=first) head++;
if(tail>=head) printf("%d\n",people[head].rp);
else printf("-1\n");
}
else if(s[]=='G') first++;
}
}
return ;
}