ural 1126. Magnetic Storms (单调队列模板题)

ural 1126
题意:n个数,求从第k个元素开始,求每k个元素的最大值(一共求n-k+1次)
思路:单调队列。
单调队列学习链接
其实单调队列挺容易的理解的。。。当时觉得写不明白大概是因为看到的代码写得太丑了2333

说下我的理解:

单调队列的尾端(就是后进入元素的那一端)其实和单调栈类似。

首端加了个元素期限的概念,不断删除“过期”的元素。

所谓过期的元素,对于这道题来说,当我往前移动到第k+1个元素的时候,第1个元素就是过期了的元素,堆答案不会再有贡献。

理论上单调队列中的元素是<元素的期限,元素>的二元组。

而一般元素的”期限”是由下标的位置决定的,而得到下标就可以知道元素。

所以我们实际操作的时候只需要将下标存入单调队列中就行了。

那么查询最大值呢? 队首元素就是最大值。

以及,用到了stl的双端队列deque(double end queue),头文件是#include <deque>

由于每次的答案是队首元素,因此设置哨兵而使得队列不为空就使得问题变得繁琐。

所以这里不同于单调栈的写法,我们不设置哨兵,而是.empty()判断双端队列是否为空。

也正是因为这个原因,没有办法像单调栈一样写成for的样子(因为没有哨兵,初始x=dq.front()的时候可能dp中还没有元素,导致RE),而是写成while的样子。。具体见代码。

 

 

 

 

作者: CrazyKK

ex-ACMer@hust,researcher@sensetime

说点什么

您将是第一位评论人!

提醒
wpDiscuz