文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > 高等教育 > 经济学 > O(n)时间的单调队列
侵权投诉

O(n)时间的单调队列

O(n)时间的单调队列

单调队列a中有n个元素,每个元素都有2个关键字:num(表示这个元素的值)和p(表示这个元素的位置)。整个单调队列都由num为关键字递减。

初始:

单调队列满足单调性。我们要求某个状态的最大值,而这个最大值要从单调队列中的元素推得,这样就可以直接取出单调队列的头元素a[1],因为a[1].num是最大的。

过程:

1.这样我们得到了一个新的状态a[n+1],它可以用来推得之后的状态。我们把它从最后面插入。和a[i]比较时(i<=n),如果a[n+1].num>a[i].num的话,a[i]这个状态就可以直接删除,因为我们有a[n+1]的话,一定不会去选比a[n+1]更劣的a[i],况且a[i]能推到的状态a[n+1]一定也能推到。因为a[i].p<a[n+1].p,当a[n+1].p不满足要求的时候,a[i].p肯定不满足要求。这样我们还会去选比a[n+1]更劣的a[i]吗?这样一直下去,a[n+1]总会在单调队列中找到一个位置使得a[j].num>a[n+1].num(或到队首)。

2.然而,a[1],甚至a[2]、a[3]都会被废弃,因为a[1].p可能不满足下个状态的要求(即a[1].p<下个状态的要求下界)。所以,我们要不断删除队首元素直到队首元素满足下个状态的要求。

结束:

a仍然满足单调性。

Head:=0; Tail:=0

For i:=1 To n Do

Begin

f[i]:=Treatment(a[Head].Num); //处理f[i]的最大值

While (f[i]>=a[Tail].Num)And(Tail>=Head) Do //删除队尾劣节点 Begin

a[Tail].Num:=0;

a[Tail].p:=0;

Dec(Tail);

End;

Inc(Tail); //添加当前节点

a[Tail].Num:=f[i]; a[Tail].p:=i; While a[Head].p<s[i+1] Do Inc(Head); End; //删除队首废弃节点

第1页

你可能喜欢

  • 国家集训队
  • NOIP2012
  • 算法合集
  • 动态规划的优化
  • 匈牙利算法
  • 归并排序

热门文档

相关文档

  • 单调队列

    单调队列 Alex Zhang 1 单调队列是指在一个队列中各个元素单调 递增(或者递减...10 【问题分析】 用堆实现的算法的时间效率是O(N*logN),虽然可以在 给定时间...

  • 单调队列

    单调队列典型程序: 滑动窗口 现在有一堆数字共 N 个数字(N<=10^6) ,以及...复杂度均为 O(nlogn),如果用有序队列维护,时间复杂度为 O(n)。 每次选取...

  • 单调队列的应用

    - 11 – 2011-08-09 COCI 2009 Ograda_题目 5、总结 单调队列的应用仍有很多实例,这一不能一一道出。 首先考虑问题需要的时间复杂度如果是 O(n)的算法,...

  • 单调队列

    单调队列作业 6页 2下载券 O(n)时间的单调队列 1页 免费 单调队列优hua ...单调队列 有n (n<1000000) 个数排成一行, 找出一段长度为 L (L<n) 的...

  • 多重背包O(NV)算法详解(使用单调队列)

    多重背包 O(N*V)算法详解(使用单调队列) 多重背包问题: 多重背包问题: 的...O(1)时间内求一个队列的最大值。 该问题可以这样解决: ① 用另一个队列 B...

  • 浅谈DP优化之单调队列优化

    K 是一个单调递减的队列,那么状态转移时我们只要取出 K 队列中下标满足要求的队首元素即可,且每个 K[i]只用入队一次出队一次 那么 时间复杂度就是 O(N)啦!...

  • 单调队列在信息学竞赛中的应用

    单调队列在信息学竞赛中的应用一、 概念介绍 1、 双端队列 双端队列是一种...单调队列队首元素为区间的最大值 End 求最小值的算法类似,大家自行设计 时间...

  • 单调队列题目汇总

    单调队列的具体作用在于,由于保持队列中的元素满足单调性, 对于上述问题中的每个 j,可以用 O(1)的时间找到对应的 s[i]。 (保持队列中的元 素单调增的话,队...

  • 单调队列

    单调队列,即单调的队列。单调队列说到底它只是一个队列而已,只不过这个队列是个有序的,也就是单调的,但是单调队 列的有序并不是排出来的,而是不断地从队尾插入...

  • 用单调性优化动态规划

    [k ,1]) + sum[i,1] ,可以发现括号内的式子 是根据 k 所确定的一个常量,直接对应上文的单调队列的方法,省掉了枚举决策 的一维,时间复杂度降为 O (n *...

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email