算法代表着用系统的方法描述解决问题的策略机制，北京大学《算法基础》课程将带你一一探索枚举、二分、贪心、递归、深度优先搜索、广度优先搜索、动态规划等经典算法，体会他们巧妙的构思，感受他们利用计算解决问题的独特魅力。顺利完成本课程，你将不但能够掌握这些算法的原理，还能够对这些算法进行灵活应用以及准确实现。本课程的中的编程任务，将充分训练你的思维能力和动手能力，促成全面、缜密思考问题的习惯。达到本门课程的要求，即意味者你具备了初步的算法基础和较强的编程实现能力。
灌溉草场（较难）
Loading...
来自 Peking University 的课程
算法基础
283 个评分
从本节课中
动态规划（1）
通过上一模块的学习，你已经了解如何通过递归的办法解决问题，但是单纯的递归往往会导致子问题被重复计算，因此在解决某些问题的时候，效率会很低。而将一个问题分解为子问题递归求解，并且将中间结果保存以避免重复计算的方法就叫做“动态规划”。本模块将初步介绍对于特定的问题如何寻找子问题、定义问题的状态以及状态转移方程。
与讲师见面
Jiaying Liu 刘家瑛, Ph.D.Associate Professor
Institute of Computer Science & Technology
郭 炜讲师
北京大学信息科学技术学院教学所
下面我们来看一道有点难度的题目，叫做这个灌溉草场
这个题目呢说的是在一片草场上，有一条长度为L的
线段，L是偶数啊，然后农夫John他有N头牛
N头牛N小于等于1000，这N头牛头都沿着草场上这条线段吃草
然后每一头牛占用了一个活动范围，这个活动范围开区间，开区间（S,E） S,E都是整数，不同奶牛的活动范围它可以是重叠的
现在John呢要在这条线段上面安装喷水头来灌溉这个草场
然后每个喷水喷洒半径可以随意调节，范围是最小 A,最大B
然后呢A,B都是整数噢，现在有一些要求，要求就是说这个线段上面每一个整点
都恰好位于一个喷水头的喷洒范围之内
然后每头奶牛的活动范围要位于一个喷水头的喷洒范围之内
你不能说有两个喷水头都喷到了同一头奶牛的活动范围，这个是不可以的
然后任何喷水头的喷洒范围不可以越过线段两端
左端就是0，右端纵向是L,分子上面不能过越过这两端
然后就问你，John最少需要安装多少个喷水头，大家自己先想一想，然后再看视频
那我们举一个 胡来事例啊，这个是线段，下面堆得这个整点
然后这边有三个喷水头，它们的喷洒范围在这
那么在这个位置2和6，就是两个
喷水头喷洒范围相邻的地方
那么在这个相邻的这一点，我们 并不认为是喷洒范围重复的这个点，它们不算重复
然后这种奶牛，这有两头奶牛c2和c1，它们的活动范围是这样
那 那么由于奶牛的活动范围它是一个开区间，所以这个一点，它并不算在奶牛的活动范围内
那我们这个第二个喷水头的这个喷洒范围就完整覆盖了 这头奶牛的这个活动范围
好，那现在的问题就是要问你最少需要多少个喷水头
输入第一行是N,L.奶牛的数目和那个线段的
最右边的这个坐标，然后第二行是整数A和B就是喷洒半径 然后接下来就是每一行都是一个奶牛的活动范围，注意它是
一个开区间，如果你找不到符合题目要求的喷水
头安装方案，那你就输出一个-1，就这么一个题目
那我们需要对这个问题进行分析，假设我们想用
纵归来解决的话，我们要把它拆分成一些子问题，对吧
子问题的规模呢，比原问题要小，子问题可以跟原问题形式一模一样
那我们假设我们从线段的起点向终点从左到右去安装这个喷水头
那很好地子问题就是我们让f(x)来表示 所安装的喷水头的喷洒范围恰好覆盖这个
直线上的区0到x的时候，最少需要多少个喷水头
这里所说的恰好就是说没有水被喷到x的右边
喷水的最大的范围正好就到达x，没有超过x的右边 那么在这种情况下最小需要多少个喷水头
那当前现在我们要求的原问题f(l)了，对吧，喷水范围不能超过l的右边嘛
那在这里，我们有一些条件可以很显然的得出
首先x肯定的是一个偶数，为什么呀，因为我们前面给的那个喷水头它有一个喷洒范围是A
喷洒的变径是A,B对吧，那也就是说，这个喷水头 它的喷洒的直径肯定就是一个偶数了
每一个喷水头它喷洒的范围肯定是个偶数，然后两个喷水头它可以淋
它喷洒范围可以紧挨在一块，但是喷洒范围不能重叠，不能叠在一块，它只能紧挨在一块
那么狠显然，只有
x为偶数的时候，它才会被某一个喷水头正好
喷到，然后它右边都没有水，是吧，x必须得是偶数 当前x所在的位置它不能出现奶牛
即x不属于任何一个奶牛活动区间S,E。
你如果x这个所在的位置这里是一个奶牛活动的
区间的话，喷水头喷水的位置正好喷到这，那下一个喷水头就从这开始喷，那这个奶牛得
活动范围就被两个喷水头所覆盖，这就不合题目的要求了，所以x它必须不属于任何一个奶头活动范围S,E。
但是x它是可以等于S也是可以等于E的，因为这个活动范围是不包含S,E。
那还有一个条件就是x肯定要大于等于2A
2A是什么，2A是 喷水头最少的
最短的这个喷洒范围，因为喷水头它的喷洒半径最少是A，对吧，所以2A就是喷水头
喷水头它喷洒的最少的这个长度
那x大于等于2A意思就是说，如果这块是2A，那么你x落在这里面的话，你肯定没有办法
安排一个喷水头，让它只喷在这，对吧，以为内一个喷水头的覆盖范围至少就是2A
你在你把你在2A这一块的左边放的任何一个喷水头它肯定都会盖到2A
所以x小于2A我们就这个f(x)
就是无解，无解就等于无穷大 这前面这几个条件都比较显然
那还有下面这个条件就对我们做纵归
非常重要的,x大于2B的时候，我们把这个x也画出来,x在这
如果有一个水龙头，它喷洒的最右边到x，那这个水龙头它喷洒到的最左边
会在哪呢，那显然就是，在范围x-2a
到x-2b之间，就是正好碰到x的那个水龙头
它碰到的最左边 就在这个范围内，也就是说正好碰到x的那个水龙头，它的左边的那个水龙头
喷洒到的最右边的范围，就是位于在这个区间内
那等价于就是说我们存在一个Y，这个Y呢它属于这个区间
这个Y呢是被某一个水龙头正好喷到的最右边
那我们在这个Y的基础上再加一个水龙头 那新加的那个水龙头，就可以正好碰到x了
那也就是说，f(x)它是等于f(y)+1的，这个Y呢
我们一定在这个区间里面能够找得到那这个Y
它，显然它的位置上也不会出现奶牛，这个Y也是偶数等等
它这个Y是正好被某一个水龙头喷洒到了
那有了这个条件以后我们就知道
可以写出这个 对f(x)计算的这个递推式子，以及初始条件的那种式子了
f(x)等于无穷大，如果x是奇数的话，f(x)就是无穷大
实际上如果x是奇数的话，我们根本就不用去算这个f(x),它没用
然后如果x小于2A，那就是说x离这个起点太近了
与起点太近的话你不可能安一个水龙头正好喷到这而且还
不出这个边界对吧，所以x小于2a的时候，f(x)就是无穷大
那如果f(x)，如果x处有奶牛出没
那我们这个x它有奶头出没，奶牛范围在这，那当然我们就不可能让一个水龙头正好喷到x对吧，所以
x如果有奶牛出没，f(x)就是无穷大 那还有一个初始条件就是f(x)等于1,
在什么时候f(x)等于1呢 就是x在2A和2B之间的时候，这是0，这是2A，这是2B
就是x在这个范围内的时候，f(x)就等于1
这是什么意思啊，就是说如果你x落在这个范围内，我肯定就只需要安一个水龙头
就能够正好喷到这个x，对吧，因为一个水龙头它的喷洒的这个
直径是2A到2B这么大，是吧
那当然这有一个x它得位于任何奶牛的活动范围之外
那前面这几条就都是边界条件或者说初始条件
那接下来我们就可以写出递推式了，递推式就是f(x)就等于1加上
里面，这么多项里面最小的那个，这里面的每一项是什么意思呢
就是对于x-2b，x-2a这个区间里面的每一个Y
如果，有一个水龙头能够正好喷洒到这个Y
那我们知道，我们再加一个水龙头就可以喷洒到x了对吧
那f(y)就是水龙头正好喷洒到Y的时候，以为内水龙头正好喷洒到Y的时候
就是所有水头龙正好覆盖范围是0到Y
所需要水龙头的最小值，那我再加一个水龙头不就能够正好碰到x了对吧
那当然正好能碰到Y的水龙头方案有好多个
其中 数量最少的那个方案就是我们想要的，我们就在这个最少的
最少的数量f(y)上面再加1，那就是正好能够碰到x的
这个方向的数目了，当然这里面有一个前提，Y它肯定得位于任何奶牛的活动范围之外，对吧
然后这边x肯定是大于2b的
好了，那有了这个递推式子，我们关键
问题就变成，我们对于每一个s对于每一个x要求f(x)的时候
我们要到这个区间， [X-2B,X-2A]这个区间里面去
寻找最小的一个f(y)，Y是属于这个区间的，
那怎么去寻找这个最小的F(Y)呢， 我们可以遍历这个区间去寻找，对吧，那遍历这个区间
需要的时间主要是多少啊，因为AB的范围是1000，所以遍历这个区间， 它所需要的时间就是1000这个量级。
而我们X一共有多少个呢？X一共有一百万个。
你每求一个F(X)你都要去在这区间里面搜一遍，那这样整个问题的时间复杂度就是这个L*B这个
区间长度，那就是一百万再乘以一千，这个
肯定会超时，太慢了。所以我们这个时候问题的关键就在于
怎么样快速的在这一个区间里面找一个
最小的F(Y)，把这个Y找到。我们不能用
遍历这个区间的办法去找这个Y，我们得像一个好办法。
遍历的话时间复杂度是O(N)的，我们应该有更好的办法。
就是我们每次都要找一堆东西里面的最小值，或者一堆东西里面的最大值，可以用什么样的数据结构呢，
哎，就可以用priority_queue， 那实际上你用multiset也可以，multiset
的begin它总是最小的，对吧，那priority_queue呢，它的对头的元素总是最大的。
但是你用一个priority_queue的时候什么叫大什么叫小你可以自己定义，对吧，
所以你等于也可以说用priority_queue，就能够实现在一堆东西里面每次找一个最小的，也是可以的。
那multiset也能解决这个问题，但是multiset总体来说用起来比priority_queue稍微慢那么一点。
好了现在我们问题就变成如果我们要求F(X)的时候，
如果我们把所有坐标属于X-2B到X-2A这个区间里面的二元组
i,F(i),i就是坐标它是属于X-2B到X-2A这个区间的，
F(i)就是它上面的F值，如果我把
所有这个区间里面的这样的二元组我们都保存在一个priority_queue里面，
而这个priority_queue呢，是根据F(I)的值排序的， 那我们就能够确保
对头的元素总是F(I)值最小的哪一个。priority_queue它自动排序，能够有这个功能，
就是priority_queue它的好处就是优先级最高的那个元素总是位于队头，
那至于什么叫优先级最高，程序员可以自己定义，在我们这个问题里面， 谁的F(I)的值小，谁的优先级就最高。
那我们，当需要求F(X)的时候，我们从 这个优先级队列，直接把队头的元素拿出来，
就能够得到我们想要的这样一个F(Y)， 得到这样一个F(Y)的值。那当然我们就
节省了这个开销，就不必是找最小值的这个步骤
就不会是O(N)了。那我们使用这个队列的时候还要注意，就是我们在
求X点的F(X)的时候，我们必须确保那个队列里面包含
所有属于X-2B到X-2A的点，
肯定的，对吧，因为一个属于X-2B到X-2A的点，
它就有可能成为上一个水龙头的
喷洒终点，而在上一个水龙头再加一个水龙头就能够到X， 那当然位于这区间内的点都不能忽略掉，
另外还要注意的就是你这个队列里面不允许出现坐标大于X-2A的点，
为什么啊，因为 坐标大于X-2A的点它对于求
F(X)是没有用的，因为你不可能让一个水龙头喷洒的范围 是位于X和X-2A之间，
然后你还能在此基础上再加一个水龙头，它正好喷洒到X，不能，为什么啊，
因为如果一个点它的坐标大于X-2A的话，那么它离X就太近了，
那么你就没有办法在这个点和X之间安排一个水龙头，使得它正好
通道X，是吧，那我们就不允许队列里面
出现这样的点，为什么呢，因为这样的点首先对求F(X)是没有用的，
而且如果这样的点出现在队列里面的话，它说不定它的F的值
会很小，对吧，有可能，对吧。如果它的F的值是最小的，那这样的点
它就会出现在队头，那我们知道priority_queue嘛，我只能访问队头元素，队里面的元素我是没有办法访问的，那如果这样一个点
它出现在队头，那这个点它的对我们求F(X)又是没有用的，
它卡在队头了，队列里面的点我们没办法访问，
那我说我把这个点从队列里面扔掉我去访问队列里面其他的点行不行啊，
不行，因为这个点它可能对求后续的F值就是X+2啊，X+4啊这些
位置的F值是游泳的，所以这样的点呢
我们不能给他扔掉，它卡在队头，然后队列里面东西你都访问不了，于是你的算法就没有办法继续下去了。
这是要注意的地方，那队列里面是不是可以出现坐标小于X-2B的点呢？
可以出现，没有关系。那如果这样的点正好出现在队头的话，
那我们直接就给他扔掉就行了，如果这样的点 还待在队列里面呢，我们也不管他，就让它待着好了。反正我们最终
要访问的都是队头的那个点，对吧，那这样的点出现在队头我们就给他扔掉拉倒，
好了，还要注意到一点就是如果我们求出了X点
的F值以后我们下一个要求F值的点就是X加上2，
对吧，那
那要求F(x+2)这个点的F值那显然
X-2A+2和X-2A，就是X-2A+2这点它的F值就肯呢过是有用的了。
那我在求X点的F值的时候，X-2A+2这个点
它实际上还并没有被换到队列里面，对吧， 因为我们前面说了，队列里面
不允许出现坐标大于X-2A的点，那当然X-2A+2就没有在队列里面，
那现在X的F点，F值求完以后，下一步要求X+2这个点的F值了，
那X+2这个点的F值它很可能就会跟这个X-2A+2有关系，所以我要把这样一个点
要给他放到队列里面，这就位了求F(X+2)做好了准备。
那当然我们队列里面主要存放坐标为偶数的点就可以了。这就是基本的解题思路。
这里面还有一个重要的问题需要解决。就是我们要求一个
X点的F(X)的时候首先我得判断这个X点是不是在奶牛的活动区间里面，
那奶牛活动区间有好多个还可以重叠，而且他们活动区间的数目是1000，对吧， 如果我们采取遍历
整个所有奶牛活动区间的方法去判断一个X点是不是在这个区间内，
那时间复杂度又变成了一百万乘以一千，那不可以接受。
那在呢么来做这件事情呢？我们边看程序边说。好，在这程序里面我先定义一个无穷大，
然后这个是L，最大取值范围，N的最大取值范围就是奶牛的数量，多取一些，
好，这个F数组就是用来
存放每一个点的F值的，那我们最终要求的答案就是F(L)，
然后这个cowThere是个一位数组，
如果cowThere[i]为1，就表示坐标为i的那个点它
位于某个奶牛的活动范围之内，那
N就是奶牛数目，L，AB就是那个喷洒的半径，
呃，然后我们刚才不是说要把那个二元组I和
F(I)放到一个priority_queue里面，对吧，所以我就定义了一个struct叫做F(X)，
它就表示这样一个二元组，这里面又坐标，以及在坐标X点的那个F 的值。
然后我们要规定一下比大小的规则。
我们得让这个priority_queue里面按照X排序，而且
在这个priority_queue里面，谁的F值小，谁的优先级就最高。
啊，那这样的话我们定义的优先级规则就是L，如果
小于号要返回TRUE的话那么我们就让这个F必须大于参数的
F值。这样我们priority_queue里面才能实现F制越小，
就越优先，当然这里面它有一个构造函数，
好接着我们看这个程序，录入了N,L,A,B,然后我们把
A和B都乘以2，因为这时候半径这个数量已经没有用了，我们关心的是那个直径，所以直接把A和B都乘以2了，
省得以后下面老写2乘以A，2乘以B，往左移就等于是，
左移一位就等于乘以2，然后我们把cowThere这个数组数字化成全0，就一开始让它所有的地方都没有奶牛，
出现是的。接下来我们 就读取所有奶牛的这个活动范围，一个奶牛的活动范围是s和e
那当我们读取一个奶牛的活动范围s和e的时候
我们对cowThere(s+1)把它++， 这意味着什么呢，意味着就说从
它被+1的话，意味着从s+1这个位置起，又进入了一个
奶牛的活动范围了，那奶牛的范围有可能重叠，对吧，所以这个位置它有可能被加到不止1，
加到不止1的话呢也就说s+1这个点它位于
不止一个奶牛的活动范围之内，就没有问题。
好了，那读到一个e我们就让cowThere[e]--，
cowThere[e]--的意思就是说，从e这个点开始就退出了一个奶牛的活动范围。
基础的意思就是这样。好了，那这个cowThere并没有被最终完成了，这只是一个 对cowThere求值的一个阶段。
那接下来我们要做的事情，啊，就是要准确的算出每一个点的这个
cowThere的值。好，我们用一个InCows的变量 表示当前点位于多少头奶牛活动范围之内。
那，那一开始InCows也是0，那没有任何当前点，没有任何奶牛的活动范围之内。
。
然后，我们从让这个点的坐标从0变到L，来计算每个点是否有奶牛。
那顺便呢我们把每个点的f值都变成无穷大，好，现在我们就让InCows+=cowThere.
那，InCows的值它本来一开始是0的，对吧？
那，那它+=cowThere [i]以后，它就有可能变成大于0了。因为cowThere
来的值可能会大一点。因为cowTher的值来的是大于0的话，就意味着从i这点开始它就进入了
若干个奶牛的活动范围之内了，对吧？那也就是InCows原来变成原来是0的，
没有在奶牛活动范围之内，加上这个以后有可能变成大于0，那也就意味着i这个点 实际上已经进入了某一个奶牛的活动范围之内。
那么，InCows呢也有可能由于这个+=就变成了0，
为什么呢？InCows有可能是，原来是，呃，
呃，大于0的，表示现在当前点是，现在反而是处在一个，或者若干个奶牛活动范围之内的。
但是，由于这个cowThere它的值有可能是负数，对吧，前面在这里边有可能把它变成负数。
变成负数的话，这个点的值，cowThere的值如果是负数的话；也就是说，当我们走到i这个点的时候我们就出了
若干个奶牛的活动范围之外，对吧，就退出了若干个奶牛挥动的范围。
那也就是说，原来在 奶牛活动的范围里面的时候，InCows可能是大于0的。然后由于+=这个
它就可能变成0，就说明出了奶牛的活动范围。
所以说我们要判断i这个点它到底有没有奶牛活动的时候
我们只需要在做完这个操作以后，再看一眼InCows是不是大于0就行了。如果
我们做完这个操作以后，InCows依然是大于的，就说明我们i这个点 它还是处于某一奶牛的活动范围之内。
对吧？如果你cowThere它的i的值 是0的话，对InCows值是没有影响的。是吧，那就说+=操作不会影响
是否在奶牛范围之内这个特性，啊，只有这个i点是
是奶牛的互动范围起点、终点的时候才会影响这个特性。那总而言之吧，
我们进入到i点的时候我们要看一下，嗯，经过这个+=操作，然後我们再看一下InCows的值。如果大于0
，就说明i这个点 还是位于某些这个奶牛活动范围之内。
如果等于0，就说明它不在奶牛活动范围之内。所以，我们就直接用InCows>0去更新了
cowThere[i]，因为这个i也是定义真的，下次再用到+=就不会用到
这个i了，啊。不会用到这个cowThere[i]了。那总之，我们通过这个循环，就解决了这个，
呃，每个i、每个点是否有奶牛这个问题。它的复杂度是O（n）.
接下来呢，我们就要初始化呢个Priority Queue，对吧？
那，我们初始化Priority Queue的时候，我们要把哪些点放进去呢？
那当然就是从A到B里面的点。A，
B，所以这里面A B都已经乘以2了，都是直径了。啊，所以现在我们
初始化队列的时候我们要考虑A到B这个区间里面的点，这个区间里面的点呢
如果这个区间里面的点i，它上面没有奶牛出没，
那这个点呢F[i]就肯定是1了，就放一个水龙头就正好把它盖到。对吧？
那我们能不能把这个，位于这个区间里面所有的
点都把它塞到这个队列里面呢？不能。因为我们前面说了，
嗯，当，因为我们下面一个要求f值的点实际上是B+2，对吧？那我们前面已经说了，
你要求点x的f值的时候，那么，嗯，
这个<x-2A的 嗯，就是说<x-2A，这
里就变成x-2A了哦。<x-A的那个点它是不应该出现在这里的。
嗯，我们下一个要除的点是B+2，对吧？所以当 我们初始化这个队列的时候啊，如果i<=B+2-A
啊，所以我们满足这个条件，我们才能把这个
点以及它的f值给它塞到这个Priority Queue里面。
如果超过了这个范围，我们就不放进去了。好，这个列队初始化完毕以后，我们就从
B+2这个点开始去求它们的 一个个点的f值，啊。在之前的点的f值我们已经初始化过了，啊。
从B+2开始往后求每个点的f值，那间隔是2，因为我们只关心偶数的点。
好，对于这样一个点i，如果没有奶牛出没
我们才去处理它，对吧？如果有奶牛出没， 那这个点的f值在前面都初始化成无穷大了，我们就不管它了。
只有在没有奶牛出没的情况下，我们才需要处理，怎么处理呢？我们就需要从刚的那个Priority
Queue qFX里面找到一个，这个，f值最小的那个点。
然後，在这个点的地图上我们加一个水龙头就能够正好盖到
这道i对吧？所以我们要在这个qFX里面找一个f 最小的这个点。
那怎么找呢？就是只要这个，嗯，队列不为空，我就取队头的 这个，元素出来把它放到FX里面。
然後我们看看，如果Fx-x<i-B，那意味了什么呀？
它离i这个点已经太远了，它太左边了。啊，那么这个点 x对于求
i已经是没有任何帮助了，因为它距离i的距离，它离i的距离都已经超过B了。
所以它对求这个f[i]是没有帮助，所以我们就直接把这个点给它扔掉了。
而且它这个点对求，求i后边的点就更加没有帮助了。所以我们就直接给它扔掉了。
那如果这个点它在合理的范围内呢？
那这个f[i]值的点就是我们需要的东西，所以我们就直接break出来就完了，
不用再去看了。那么Break了出来以后呢，我们这里要判断一下这个Break到底是由于队列空了；
还是由于找到了一个合适的值所导致的。如果是由于队列的空导致的话，
那就说明我们根本就没有找到一个什么合适的前据的点Fx。那这个时候
f[i]的值就让它无穷大好了。那我们就不处理它了，因为之前已经变成无穷大了。
那么在这个，呃，Break出来是因为找到了一个
合适的Fx的情况下，那我们这个f[i]
它的值当然就等于Fx里面的f的值再+1。对吧？
这个Fx里面的这个x是上一个水龙头
正好喷洒到的那个右边键，然后我们在此地图上再加一个水龙头
就能够喷洒到i，所以呢，这个F[i]=fx.f+1。
然後，还有一件事情不要忘了，
在刚才这个我们已经求出来f[i]的值，那下一次我们要求的 当然就是f[i],
F-(i+2)的值，对吧？ 你要求F-(i+2)的值的时候，这个i+2-A
这个点是有用的，可是，这个点刚才还不在队列里面。
所以我现在接下去要做的事情，就是把这个点往队列里面放。
嗯，那这个点它的F值实际上是已经求出了对吧？ 好，那么，我就要看这个点的F值它是不是无穷大，
如果不是无穷大的话，诶，我就要把这个点往里面放。所以就qFxpush一个
这个2元素，它的坐标是i-A+2。
呃，它的值是i-A+2。
好，就这么不停的做循环，然後，到循环结束的时候，Fl就是我们想要的东西了。
如果Fl还是无穷大，就说明我们还是找不到合适的放水龙头的方案。
所以我们就输出一个-1。呃，如果它不是无穷大，那我们就把它的值输出，那就是问题的解。
那这个整个程序它的时间复杂度是多少呢?
我们看在这个地方有一循环，对吧？那前面已经有循环是O(n)了是吧？反正至少就是O(n)。
然後我们看看这里有一个循环，这个循环当然是O(n)的。然後在这个循环里面呢，我们每次都要去找一个，这个，
呃，队列里面的这个，呃，
最优值拿出来，对吧？那么从队列里面拿出最优值，这个复杂度是O(1)的，啊。
但是我们后面还有这个，从队列里面把队头的元素给弹出来合格操作。
这个操作在Priority Queue里面的复杂度是log n的。这个n是队列 里面的元素个数。
那么我们有没有可能在这个内存循环里面
做很多，很多次的这个操作，那就会导致整个的复杂度变得很高呢？ 大家放心，不存在这个问题。为什么呢？因为
大家想想在这个题目里面，每一个点都只会进队列一次，出队列一次。
嗯，有的时候还不出队列，对吧？那也就是说每个点最多出队列次。因此说
一共也只有l个点，所以这个pop的操作它最多也就是被执行l次。
那我们这个外存循环一共就有l次，
pop的操作最多执行也l次。那好像在内存循环里面，在这个内存循环里面pop的平均就被执行一次。
呃，所以说，整个问题时间复杂度就是这个，这个Lxlogn,
这个logn是队列里面的元素个数。那队列里面的元素个数，呃，大概是什么范围呢？
嗯，大概就是B的范围，就是1000然而你也可以认为在很高的情况下
也许，嗯，全部的点都跑到队列里面，我们做最最
这个悲观的这个估计吧！那队列里面的元素个数也只不过是L。那整个问题的复杂度呢，呃，在这块儿
也就是LxLogL 对吧？然后我们再看到，这边还要执行push的操作。push操作，
它的复杂度也是LogL。我们最坏的考虑来算吧，也就是logL。
嗯，所以，是说我们整个的，嗯，程序它的复杂度是LlogL.
这里写个n，n就是L的意思。
Ok，那，前面我们提到过在人人为我这种类型的顿规程序里面，
在执行人人为我这一步的时候，
我们可以采取一些好的数据结合的算法，我们就可以不需要编译那个所有的人人。
结果能够在这些人人里面找到一个最优值， 然後在这个议题里面，就很好的组合了前面说的这种情况。
在这里，我们用一个Priority Queue 去选取最优点，而不需要去编译
所有可能点。
