博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
hdu 3415
阅读量:6403 次
发布时间:2019-06-23

本文共 534 字,大约阅读时间需要 1 分钟。

单调队列即保持队列中的元素单调递增(或递减)的这样一个队列,可以从两头删除,只能从队尾插入。单调队列的具体作用在于,由于保持队列中的元素满足单调性,对于上述问题中的每个j,可以用O(1)的时间找到对应的s[i]。(保持队列中的元素单调增的话,队首元素便是所要的元素了)。

维护方法:对于每个j,我们插入s[j-1](为什么不是s[j]? 队列里面维护的是区间开始的下标,j是区间结束的下标),插入时从队尾插入。为了保证队列的单调性,我们从队尾开始删除元素,直到队尾元素比当前需要插入的元素优(本题中是值比待插入元素小,位置比待插入元素靠前,不过后面这一个条件可以不考虑),就将当前元素插入到队尾。之所以可以将之前的队列尾部元素全部删除,是因为它们已经不可能成为最优的元素了,因为当前要插入的元素位置比它们靠前,值比它们小。我们要找的,是满足(i>=j-k+1)的i中最小的s[i],位置越大越可能成为后面的j的最优s[i]。

在插入元素后,从队首开始,将不符合限制条件(i>=j-k+1)的元素全部删除,此时队列一定不为空。(因为刚刚插入了一个一定符合条件的元素)

转载于:https://www.cnblogs.com/acm-jing/p/4393023.html

你可能感兴趣的文章
yii框架常用url地址
查看>>
python3.4学习笔记(十六) windows下面安装easy_install和pip教程
查看>>
MyGUI 解析
查看>>
Linux中的ls命令详细使用
查看>>
graph-tool文档(一)- 快速开始使用Graph-tool - 2.属性映射、图的IO和Price网络
查看>>
easyui treegrid逐步加载
查看>>
GraphicsLab Project之辉光(Glare,Glow)效果 【转】
查看>>
<转>Python: __init__.py 用法
查看>>
Linux Curl命令
查看>>
046 SparlSQL中的函数
查看>>
-27979 LoadRunner 错误27979 找不到请求表单 Action.c(73): Error -27979: Requested form not found...
查看>>
[LeetCode] Minimum Depth of Binary Tree
查看>>
,net运行框架
查看>>
Java 中 Emoji 的正则表达式
查看>>
Mixin Network第一届开发者大赛作品介绍- dodice, diceos和Fox.one luckycoin
查看>>
安卓Glide(4.7.1)使用笔记 01 - 引入项目
查看>>
中金易云:为出版社找到下一本《解忧杂货店》
查看>>
Flex布局
查看>>
Material Design之 AppbarLayout 开发实践总结
查看>>
Flutter之MaterialApp使用详解
查看>>