fzu-1894 志愿者选拔-单调队列

转战单调队列，争取省赛前做完。。。。

这个题是很裸的单调队列。

不能用stl让人很蛋疼。。。。

就是用一个队列保存当前队伍的信息，如果来了一个大的，就把前面的小的挤掉。

#include
  
   
#include
   
     #include
    
      #include
     
       #include
      
        #include
       
         using namespace std; #define maxn 55000 #define INF 99999999 struct list { char name[6]; int val; int ip; }peo[1000000],p; int main() { int T,i,j; char str[1100]; scanf("%d",&T); while(T--) { scanf("%s",str); int head=1; int wei=0; int st=1; for(i=1;;) { scanf("%s",str); if(str[0]=='C') { scanf("%s %d",p.name,&p.val); p.ip=i; for(j=wei;j>=head;j--) { if(peo[j].val<=p.val)wei--; else break; } wei++; peo[wei]=p; i++; } else if(str[0]=='G') { if(peo[head].ip==st)head++; st++; } else if(str[0]=='Q') { if(head>wei) { printf("-1\n"); continue; } printf("%d\n",peo[head].val); } else break; } } return 0; }