练习题：特殊队列

本文主要是介绍练习题：特殊队列，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

题面

给定一个特殊的队列，支持如下操作：

$ENQUEUE X$：入队一个整数$X$；

$DEQUEUE$：出队一个元素；

$REVERSE$：对队列的每个元素取反，即$X$变为$-X$；

$MAXIMUM$：取队列中值最大的元素，若队列为空则忽略该操作。

输入格式:

第一行为正整数$T$，表示测试数据的组数。对于每组测试数据，第一行为一个正整数$n$，表示操作的个数，接下来$n$行，每行表示一个操作。$T$不超过$10$，$n$不超过$2×10^6$。

输出格式:

对于每一个未被忽略的$MAXIMUM$操作，输出该操作的返回值。每组测试数据的结果间隔一个空行。

输入样例:

1
6
ENQUEUE -8
REVERSE
ENQUEUE -5
MAXIMUM
DEQUEUE
MAXIMUM

输出样例:

8
-5

分析

发现需求的操作里有明确写出入队出队，先考虑使用队列。因为询问的是一个队列内的现存最大值，所以考虑用单调队列来维护这个最大值，$ENQUEUE$、$DEQUEUE$、$MAXIMUM$三个操作都是单调队列已经实现的操作，所以只需要考虑$REVERSE$操作的处理即可。

前方要讨论$REVERSE$操作，所以，以下两个等式很有用：$$max(-a,-b) = -min(a,b)$$ $$max(-a,-b,-c,...,x) = -min(a,b,c,...,-x)$$

SDDF 2021/10/18 19:39:06
因为有reverse操作，取相反数之后最小值和最大值反转，考虑用两个队列分别维护队列最大值和队列最小值

SDDF 2021/10/18 19:40:00
分析reverse操作：将所有队内数取相反数，未入队的不取

SDDF 2021/10/18 19:40:38
若朴素地遍历整个队列取相反数，复杂度太大不满足要求

SDDF 2021/10/18 19:41:32
考虑到如下等式 max(-a,-b) = -min(a,b)

SDDF 2021/10/18 19:42:12
我们发现，可以将相反数队列的最大值转化为求原队列的最小值

SDDF 2021/10/18 19:42:36
同时考虑在reverse后又有新元素入队的情况

SDDF 2021/10/18 19:42:48
有如下等式：

SDDF 2021/10/18 19:43:35
max(-a,-b,-c,-..., x) = -min(a,b,c,..., -x)

SDDF 2021/10/18 19:43:51
（x是新入队的元素，没有被reverse）

SDDF 2021/10/18 19:44:45
可见，只需要在reverse状态下将新入队元素取相反数，即可保证查询到的max仍然正确

SDDF 2021/10/18 19:45:53
若发生偶数次reverse，则后续的操作就和没有reverse过一样

SDDF 2021/10/18 19:46:33
所以只需要打一个bool标记，记录当前是奇数次reverse还是偶数次

SDDF 2021/10/18 19:47:29
如上，reverse操作已经可以被处理，其他三个操作只需要按照单调队列（优先队列）的功能写即可

这篇关于练习题：特殊队列的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！