Massive Algorithms: foj 1894 - 志愿者选拔

http://www.voidcn.com/article/p-tpbotvnl-bc.html

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

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

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

作为主面试官的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

Hint

数据较大建议使用scanf,printf 不推荐使用STL

在学习单调队列优化DP之前有必要学习单调队列是什么东西@。@ 本题实现了插入数据、询问最大值、删除队首元素（题中排队的队首，不是维护队列的队首）的功能，智商捉急的我从早上看到现在才明白==

维护的队列队首是L,队尾是R,每插入一个数据，都使得队列单调递减（因为这题要求最大值，求最小值的话就单调递增呗），具体做法考虑是先假设在一个已经维护好的队列上插入，从后往前遍历队列，遇到比待插入数据小的替换，队列后面的部分截掉；

再说查询，很明显取队首元素，但是需要判断队首是否还在233333；

纠结了好半天的是删除最先来的out是啥意思，写了数据模拟才明白。我们首先得知道维护的队列有一个特殊性质：如果有一个后来的元素插进去了，那么之前序号比他小、值也比他小的就被截断舍弃了，虽然他们没有被移除出实际排的队伍，但是由于对于我们取最大值没有必要，我们不用再去维护他。。再说这个题， out小于队列首元素序号的时候，说明删掉的是我们已经放弃维护的对象，反正对于最大值的维护也没有必要，删了就删了，但是需要++out；当out>队首元素时，才有必要真的把队首元素移除，根据手工模拟队列的思想，l++即可

int rp[mm],q[mm];
char name[10],op[10];
int main()
{
  //  freopen("cin.txt","r",stdin);
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int l=0,n=0,out=0,r=-1;
        while(scanf("%s",op),op[0]!='E')
        {
            if(op[0]=='C')
            {
                ++n;
                scanf("%s%d",name,&rp[n]);//取地址符能忘写！
                while(l<=r&&rp[q[r]]<rp[n]) r--;
                q[++r]=n;
            }
            if(op[0]=='G') (++out>=q[l])?l++:l;
            if(op[0]=='Q') printf("%d\n",out<n?rp[q[l]]:-1);//队列可能空！！
        }
    }
    return 0;
}

https://www.cnblogs.com/neverforget/archive/2011/10/13/ll.htm

题目本身就是队列，由于要找的是最大值，我们自然想到用单调队列解决问题。

维护一个单调递减序列，只需输出序列中的第一个元素即可。

对于命令我们可以进行不同的处理：

如果是Q命令，则判断当前队列中是否仍有元素，如果没有则输出-1，如果有则直接输出队首。

如果是G命令，则对last加1，之后对于队列中所有超出范围的前端元素进行出队操作。（该元素在原序列中的位置>=last）

如果是C命令，则将该元素加入队列中，并和队尾元素比较，维护队列的单调性。

这里考虑一个问题，当前元素加如后对队尾元素为什么可以毫无保留的删去呢？

因为当前加入的元素比队尾元素大，且该元素比队尾元素入队晚（也就是该元素比队尾元素晚出队），所以只要该元素在队列中，就一定不会选取队尾元素。也就是当前状态一定比队尾元素的状态更优。——这里一定要理解深刻，这是队列的本质。

因此，这题的单调队列中维护的一个属性是元素的价值，一个属性是单调队列中的元素在原序列中的位置。

注意，q中的值是该元素在原序列中的位置！

foj 1894 - 志愿者选拔 - Monotone Queue

Labels

Popular Posts