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
#include
#define maxn 1000000

struct 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
,q[head].val);
                else printf(-1
);
            }
            else last++;
        }
    }
    return 0;
}