版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
从一类单调性问题看算法优化长沙市一中
汤泽1/31充分挖掘数据关系,灵活利用数据结构,往往是结构出优异算法关键原因普通队列:一端插入,另一端删除特殊队列:尾端插入,两端删除单调性:帮助优化一类单调性问题2/31问题1锯木厂选址2<=N<=0,1<=Wi<=10000,1<=Di<=10000123112112131261213W:N=9D:3/31问题1锯木厂选址最优方案中,锯木厂必定建在有树位置4/31问题1锯木厂选址123112112131261213W:N=9D:123112112131261213W:N=9D:0012345678910Sd02367915161819Sw13671011131415155/31问题1锯木厂选址分析:C[I]:在第I棵树处建立一个锯木厂,而且将第1到第I棵树全部运到这个锯木厂所需费用W[J,I]:在第I棵树处建立一个锯木厂,而且将第J+1到第I棵树全部运往这个锯木厂费用
6/31问题1锯木厂选址分析:F[I]表示在第I棵树处建立第二个锯木厂最小费用,则:这个算法时间复杂度为O(N^2)7/31问题1锯木厂选址
I
JI+1
J8/31问题1锯木厂选址证实:令S[K,I]表示决议变量取K时F[I]值
设K1<K2<I,S[K1,I]-S[K2,I]<0
9/31问题1锯木厂选址证实:设K1<K2<I,S[K1,I]-S[K2,I]<0令g[K1,K2]=上面不等式左边
因为D[K]≥0,所以Sd序列不下降
所以决议是单调!10/31问题1锯木厂选址分析:
维护一个特殊队列K,K1<K2<…<Kn,g[K1,K2]<g[K2,K3]<…g[Kn-1,Kn]:计算状态F[I]前,若g[K1,K2]<=Sd[I],表示决议K1不比K2优,删除K1,重复该步骤11/31问题1锯木厂选址分析:计算F[I],F[I]=C[K1]+W[K1,I]+W[I,n+1]若g[Kn-1,Kn]>g[Kn,I],Sd[I’]>g[Kn-1,Kn]>g[Kn,I]Kn比Kn-1优之前I就将比Kn优,删除Kn,重复该步骤,最终将I插入队列
算法总复杂度O(N)12/31问题2旅行问题问题描述:一个环形跑道上有n个加油站,按顺时针编号为1到n(3<n<10^6)第i号加油站有Pi(0<=Pi<10^9)升汽油,每升汽油可供行驶一千米第i号车站到其下一站距离为Di(0<di<10^9)13/31问题2旅行问题一个例子:N=5P[1]=3;D[1]=1P[2]=1;D[2]=2P[3]=5;D[3]=2P[4]=0;D[4]=1P[5]=5;D[5]=4315051221414/31问题2旅行问题一个例子:N=5P[1]=3;D[1]=1P[2]=1;D[2]=2P[3]=5;D[3]=2P[4]=0;D[4]=1P[5]=5;D[5]=4S=3S=3S=6S=4S=8S=2S=1S=4S=3S=4以1号加油站为起点15/31问题2旅行问题一个例子:N=5P[1]=3;D[1]=1P[2]=1;D[2]=2P[3]=5;D[3]=2P[4]=0;D[4]=1P[5]=5;D[5]=4S=1以2号加油站为起点S=-116/31问题2旅行问题一个例子:N=5P[1]=3;D[1]=1P[2]=1;D[2]=2P[3]=5;D[3]=2P[4]=0;D[4]=1P[5]=5;D[5]=4S=1S=0S=-1以2号加油站为起点S=317/31问题2旅行问题一个例子:N=5P[1]=3;D[1]=1P[2]=1;D[2]=2P[3]=5;D[3]=2P[4]=0;D[4]=1P[5]=5;D[5]=4以1、3、5号加油站为起点有方法周游一圈18/31算法一分析:直接模拟刚才演算过程总时间复杂度为O(N^2)
不过N最大能够到达10^6!太慢了!19/31算法二分析:假定只能按顺时针方向行驶.令A[I]=P[I]-D[I]A[I+N]=A[I]A[0]=0
设SA[I]表示A序列中前I项和20/31算法二0123456789A02-13-112-13-1sa021434658712345P31505D1221421/31算法二分析:SA[I]到SA[I+N-1]都大于SA[I-1]SA[I]到SA[I+N-1]中最小数大于SA[I-1]
求N个数中最小数,很自然地想到了堆!22/31算法二0123456A02-13-112Sa021434612434134413464堆中不超出N个元素2N次插入操作2N次删除操作N次取堆顶元素总复杂度O(NLog2N)23/31算法三分析:给定一个序列SA和N个区间求出每个区间中最小值,对其作对应判定
这是一个标准RMQ问题!时间复杂度降为O(N)SA:0214342143
24/31算法四分析:
给定N个区间不存在包含关系,满足单调性!
0123456789Sa:0214342143
K:
22777一样满足单调性?25/31算法四预处理:维护一个特殊队列K,K1<K2<…<KnSa[k1]<Sa[k2]<…Sa[Kn]将1,2…n-1依次插入队列K.插入前,假如Sa[i]<=Sa[kn],将Kn删除.重复该步骤,最终将i插入队列26/31算法四求解并更新K:若K1=i-1,将K1删除出队列插入新位置号i+n-1,若Sa[Kn]>=Sa[i+n-1],删除Kn,重复这个步骤,最终将i+n-1作为Kn插入队列若Sa[k1]>=Sa[i-1],表示从i号加油站出发能够周游一周总复杂度O(N)27/31四个算法比较空间复杂度时间复杂度实现难度算法一O(N)O(N^2)很轻易算法二O(N)O(Nlog2N)
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 雷锋的故事读后感400字10篇
- 霹雳贝贝的读后感800字左右
- 教师典型先进事迹材料(10篇)
- 荧光亮度检定仪检定规程
- 证券投资技术分析(第七版) 课件 RTS
- 高职自我鉴定7篇
- 培训师创业心得体会8篇
- 大班数学找规律教案5篇
- 全球变化生态学答案
- 2024四川达州渠县人民法院招聘聘用制书记员(3人)笔试备考题库及答案解析
- 2024-2030全球及中国服务集成与管理(SIAM)行业市场发展分析及前景趋势与投资发展研究报告
- 2024年济南市高三二模地理试卷(含答案详解)
- 肺炎合并糖尿病的全面护理查房
- 2024年1月浙江省普通高校招生选考物理试题和答案
- 小学二年级乘除法口算题直接打印版
- 2024版人教版英语初一上单词表
- 人工智能时代的挑战与机遇
- 江苏南通如东县2022-2023学年第二学期期末二年级语文学情调查练习
- “高空安全作业培训课件”
- 学生心理健康一生一策档案模板
- 2024年山东临沂市直部分医疗卫生事业单位招聘854人历年高频考题难、易错点模拟试题(共500题)附带答案详解
评论
0/150
提交评论