FZU 1894（单调队列第一发）

本文主要是介绍FZU 1894（单调队列第一发），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意：参加志愿者选拔的同学们排队接受面试官们的面试。参加面试的同学们按照先来先面试并且先结束的原则接受面试官们的考查。 
 
输入
含义
1
C
NAME RP_VALUE
名字为NAME的人品值为RP_VALUE的同学加入面试队伍。(名字长度不大于5，0 <= RP_VALUE <= 1,000,000,000)
2
G
排在面试队伍最前面的同学面试结束离开考场。
3
Q
主面试官John想知道当前正在接受面试的队伍中人品最高的值是多少。

思路：直接维护一个单调递减序列，那么序列首就是最大值。因为是按照先来先走的规则，所以每一次更新的话把原来的在此位置的那个人舍弃掉。

#include<stdio.h>
#include<string.h>
#define maxn 1000000struct node{int x,val;
}q[maxn];int main()
{int t;char name[6],na[10],start[12];int rp;scanf("%d",&t);while(t--){int i,j,k,head=0,tail=-1,last=0,K=1;scanf("%s",start);while(scanf("%s",name)!=EOF){if(strcmp(name,"END")==0) break;if(name[0]=='C'){scanf("%s%d",na,&rp);while(tail>=head&&q[tail].val<=rp) tail--;node a;a.x = K++;a.val = rp;q[++tail]=a;}else if(name[0]=='Q'){while(tail>=head&&q[head].x<=last) head++;if(tail>=head) printf("%d\n",q[head].val);else printf("-1\n");}else last++;}}return 0;
}

这篇关于FZU 1894（单调队列第一发）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---