Java教程

练习题:特殊队列

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

题面

给定一个特殊的队列,支持如下操作:

$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操作已经可以被处理,其他三个操作只需要按照单调队列(优先队列)的功能写即可

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