算法合集之《从一类单调性问题看算法的优化》省公开课金奖全国赛课一等奖微课获奖课件

从一类单调性问题看算法优化长沙市一中

汤泽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)