FZU 1894 志愿者甄拔（单调队列）

FZU 1894 志愿者选拔（单调队列）

Description

世博会马上就要开幕了，福州大学组织了一次志愿者选拔活动。

参加志愿者选拔的同学们排队接受面试官们的面试。参加面试的同学们按照先来先面试并且先结束的原则接受面试官们的考查。

面试中每个人的人品是主要考查对象之一。（提高人品的方法有扶老奶奶过街，不闯红灯等）

作为主面试官的John想知道当前正在接受面试的同学队伍中人品值最高的是多少。于是他请你帮忙编写一个程序来计算。

Input

输入数据第一行为一整数T，表示有T组输入数据。

每组数据第一行为”START”，表示面试开始

接下来的数据中有三种情况：

	输入	含义
1	C NAME RP_VALUE	名字为NAME的人品值为RP_VALUE的同学加入面试队伍。(名字长度不大于5，0 <= RP_VALUE <= 1,000,000,000)
2	G	排在面试队伍最前面的同学面试结束离开考场。
3	Q	主面试官John想知道当前正在接受面试的队伍中人品最高的值是多少。

最后一行为”END”，表示所有的面试结束，面试的同学们可以依次离开了。

所有参加面试的同学总人数不超过1,000,000

Output

对于每个询问Q,输出当前正在接受面试的队伍中人品最高的值,如果当前没有人正在接受面试则输出-1。

Sample Input

2STARTC Tiny 1000000000C Lina 0QGQENDSTARTQC ccQ 200C cxw 100QGQC wzc 500QEND

Sample Output

10000000000-1200100500

题意：就是一系列操作和询问，每次询问问你当前队列的最大值。

分析：我们可以维护一个单减队列，每次取最大值可以在队列首取出来。

但是有一点就是每当有人出队的时候如何判断队首的数据已经过期。

我们知知道在维护单调性的时候，数据的进入都是有先后顺序的，后面的数据

要是想要到队首，必须把前面的数据清除掉，所以可以保证队列从前到后

数据的（进队顺序）都是递增的。我们可以给队列的每个点加一个计数，对出队的人计数，

如果相等，表示队首数据过期。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<string>
#include<iostream>
#include<queue>
#include<cmath>
#include<map>
#include<stack>
#include<set>
using namespace std;
#define REPF( i , a , b ) for ( int i = a ; i <= b ; ++ i )
#define REP( i , n ) for ( int i = 0 ; i < n ; ++ i )
#define CLEAR( a , x ) memset ( a , x , sizeof a )
const int INF=0x3f3f3f3f;
typedef long long LL;
const int maxn=1e6+100;
struct node{
    int val;
    int id;
}q[maxn];
int t;

int main()
{
    char str[10];
    int x;
    scanf("%d",&t);
    while(t--)
    {
        int head=1,tail=0;
        int cnt=0,pos=0;
        while(~scanf("%s",str)&&strcmp(str,"END")!=0)
        {
            if(str[0]=='C')
            {
                scanf("%s%d",str,&x);
                while(head<=tail&&q[tail].val<=x)
                    tail--;
                q[++tail].val=x;
                q[tail].id=++cnt;
            }
            else if(str[0]=='G')
            {
                pos++;
                if(pos==q[head].id)
                    head++;
            }
            else if(str[0]=='Q')
            {
                if(head<=tail)
                    printf("%d\n",q[head]);
                else puts("-1");
            }
        }
    }
    return 0;
}

FZU 1894 志愿者甄拔（单调队列）

相关推荐