从一类单调性问题看算法的优化（汤泽）

2006年全国信息学冬令营讲座

从一类单调性问题看算法的优化

湖南省长沙市第一中学 汤泽

【关键字】

数据关系 队列 单调性 【摘要】

充分挖掘数据关系，往往是构造出优秀算法的关键因素。本文从单调性入手，详细讨论了允许在表的尾端进行插入，而在两端删除元素的特殊队列对一类单调性问题的优化方法，并以此说明充分利用数据关系对构造优秀算法的重要性。

【正文】

对于很多问题，如果我们充分挖掘问题当中隐含的数据关系，并对某些简单的数据结构作出相应变形，应用于这些数据关系，就能以较低的编程复杂度来实现算法的优化。本文将通过一种特殊队列在一类单调性问题中的运用，来讨论这种思想的具体应用。

队列是一种我们非常熟悉的数据结构。最常见的队列是一种先进先出的线性表：它只允许在表的一端进行插入，而在另一端删除元素。我们对这种常见队列稍作变形，构造出一个特殊队列：它允许在表的尾端进行插入，而在两端删除元素。对于一些问题，如果能够挖掘出问题中隐含的单调关系，这种特殊队列能够很好地帮助我们完成算法的优化。

一、 在动态规划问题中的应用

运用单调性和这种特殊队列进行优化的例子最常见于动态规划问题当中。有些动态规划问题，可以利用决策的单调性，运用这种特殊队列来实现“降一维”。下面是一个具体的问题。

【问题一】锯木场选址（CEOI2004）

从山顶上到山底下沿着一条直线种植了n棵老树。当地的政府决定把他们砍下来。为了不浪费任何一棵木材，树被砍倒后要运送到锯木厂。

1

2006年全国信息学冬令营讲座

木材只能按照一个方向运输：朝山下运。山脚下有一个锯木厂。另外两个锯木厂将新修建在山路上。你必须决定在哪里修建两个锯木厂，使得传输的费用总和最小。假定运输每公斤木材每米需要一分钱。 任务

你的任务是写一个程序：

从标准输入读入树的个数和他们的重量与位置 计算最小运输费用 将计算结果输出到标准输出 输入

输入的第一行为一个正整数n——树的个数（2≤n≤20 000）。树从山顶到山脚按照1，2??n标号。接下来n行，每行有两个正整数（用空格分开）。第

i+1行含有：wi——第i棵树的重量（公斤为单位）和 di——第i棵树和第i+1棵树之间的距离，1≤wi ≤10 000，0≤di≤10 000。最后一个数dn，表示第n棵树到山脚的锯木厂的距离。保证所有树运到山脚的锯木厂所需要的费用小于2000 000 000分。 输出

输出只有一行一个数：最小的运输费用。 样例

输入 9 1 2 2 1 3 3 1 1 3 2 1 6 2 1 1 2 1 1 输出 26

在解决这一问题时，首先我们要明确，将锯木厂建立在相邻两棵树之间是没有任何意义的，否则我们可以将这样的锯木厂上移到最近的一棵树处，此时运送上方树木的费用减少，运送下方树木的费用没有变化，总费用降低。

为了方便讨论，我们先作如下定义：

2

2006年全国信息学冬令营讲座

假设山脚锯木场处也有一棵树，编号为n?1，并且w[n?1]?d[n?1]?0。

sumw[i]表示第1棵树到第i棵树的质量和，即sumw[i]??w[j]。

j?1isumd[i]表示第1棵树到第i棵树的距离，即sumd[i]??d[j]。特别的，有

j?1i?1sumd[1]?0，表示第1棵树到自己的距离为0。

c[i]表示在第i棵树处建一个锯木厂，并且将第1到第i棵树全部运往这个[i?1]?d[i?1]。伐木场所需的费用。显然有c[i]?c[i?1]?sumw特别的，有c[1]?0。

w[i,j]表示在第i棵树处建一个锯木场，并且将第j?1到第i棵树全部运往[j]?(sumd[i]?sumd[j])。特这个锯木场所需的费用。则w[i,j]?c[i]?c[j]?sumw别的，当i?j时w[i,j]?c[i]。

[i],sumd[i]与c[i]的时间复杂度为O(n)，此后求综上可知，求出所有sumw任意w[i,j]的时间复杂度都为O(1)。 设f[i]表示在第i棵树处建立第二个锯木场的最小费用，则有

f[i]?min{c[j]?w[i,j]?w[n?1,i]}。直接用这个式子计算的时间复杂度为

1??j?i?1O(n2)，由于问题规模太大，直接使用这一算法必然超时，因此我们必须对算法进行优化。在讨论如何进行优化以前，我们首先证明下面这一猜想。 [猜想] 如果在位置i建设第二个锯木厂,第一个锯木厂的位置是j时最优。那么如果在位置i?1建设第二个锯木厂,第一个锯木厂的最佳位置不会小于j。 证明：

令s[k,i]表示决策变量取k时f[i]的值，即s[k,i]?c[k]?w[i,k]?w[n?1,i]。 设k1?k2，则有

s[k1,i]?s[k2,i]?sumw[k2]?(sumd[i]?sumd[k2])?sumw[k1]?(sumd[i]?sumd[k1]) 3

2006年全国信息学冬令营讲座

若s[k1,i]?s[k2,i]?0，则有

sumw[k2]?(sumd[i]?sumd[k2])?sumw[k1]?(sumd[i]?sumd[k1])?0

将含K的项移到不等式左边，整理得

(sumw[k1]?sumd[k1]?sumw[k2]?sumd[k2])/(sumw[k1]?sumw[k2])?sumd[i] 我们令g[k1,k2]?不等式左边，当g[k1,k2]?sumd[i]时s[k1,i]?s[k2,i]?0。因为d[k]?0，所以对于j?i有g[k1,k2]?sumd[i]?sumd[j]。

证毕。

由上面的证明，可以说明决策变量j是单调的，此时问题就好解决了。我们可以维护一个特殊的队列k，这个队列只能从队尾插入，但是可以从两端删除。这个队列满足k1?k2?k3?...?kn以及g[k1,k2]?g[k2,k3]?...?g[kn?1,kn]。

1．计算状态f[i]前，若g[k1,k2]?sumd[i]，表示s[k1,i]?s[k2,i]?0，即决策k1没有k2优，应当删除，直至g[k1,k2]?sumd[i]。

2．计算状态f[i]时，有f[i]?c[k1]?w[i,k1]?w[n?1,i]。

3．计算状态f[i]后向队列插入新的决策i。若g[kn?1,kn]?g[kn,i]，表示在kn比kn?1优之前i就将比kn优，kn没必要保存。因此删除kn，直至

g[kn?1,kn]?g[kn,i]。 每个状态f[i]计算的复杂度都为O(1)，维护队列k的总复杂度为O(n)，因此整个算法的时间复杂度为O(n)。问题得到解决！

本例直接利用决策的单调性，运用这一特殊的队列成功地将算法的复杂度降低，而有的动态规划问题，虽然表面上看起来决策不单调，无法直接套用上面介绍的优化方法，但是只要充分挖掘条件中隐含的单调关系，并对数据作出相应的调整变形，仍然可以利用类似的方法实现时间上的“降维”。

【问题二】货币兑换（BOI2003）

你每天会收到一些货币A，可能正也可能负，银行允许你在某天将手头所有的货币A兑换成B。第i天的兑换比率是1 A ：i B，同时你必须再多付出t B被银行收取。在N天你必须兑换所有持有的货币A。

4

2006年全国信息学冬令营讲座

任务

找一个方案使第N天结束时能得到最多的货币B 输入文件

第一行是整数N,T

第二行是N个整数Ai，表示第i天开始时得到Ai的A币 输出文件

将最终得到的最多的B货币数写到文件 数据范围

? 1 ≤ N ≤ 34 567 ? 0 ≤ T ≤ 34 567

样例输入 7 1

-10 3 -2 4 –6 2 3 样例输出 17

我们很容易得到问题的基本解决方法： 定义suma[i]表示第一天到第i天总共得到了多少A币，特别的，有

suma[0]?0

w[i,j]表示以第i天作为一个分割点，并且将第j?1天到第i天得到的A币进

行一次性兑换可以得到的B币数。则w[i,j]?(suma[i]?suma[j])*i，特别的，当

i?j时，有w[i,j]?a[i]*i。

求出所有suma[i]的时间复杂度为O(n)，此后求任意w[i,j]的时间复杂度都为O(1)。

设f[i]表示以第i天作为一个分割点，最多可以得到多少个B币。则

f[i]?min{f[j]?w[i,j]}?T。直接用这个式子计算的时间复杂度为O(n2)，不

0??j?i?1能满足要求。

由于本题中a[i]可正可负，使得suma不满足单调性，只要推倒一下就会发现，我们不能像上一题一样证明出决策的单调性。因此我们好像无法采用上例中

5

2006年全国信息学冬令营讲座

相同的方法来实现“降一维”。

但我们很自然地联想到，如果可以通过一定的变换，将Ai的值变为全部非负或者非正，问题就迎刃而解了。

注意到这样一个条件：第i天的兑换比率是1 A ：i B，也就是说，时间越往后，A币越值钱。也就是说，A币兑换B币的比率是单调的！

利用这一重要条件作为突破口，考虑一种贪心的思想：如果当前手上的A币数为正，那么我们可以不忙着将其换成B币，因为留到以后再换，不但可以减少T的消耗，还可以使得兑换的比例更高。基于这种思想，我们很自然地得到了如下猜想。 [猜想]

若{ai}序列中有一段连续的子序列a[i],a[i+1]......,a[j](i

a[i]，a[i]?a[i?1]，a[i]?a[i?1]?a[i?2],??a[i]?a[i?1]?.....?a[j?1]，[]?ai[?1]?...[]aj均为非负数，而ai为负数，则当在第i天收到了a[i]的货币

A后，一定存在某个最优方案，使得我们不急于在第i天兑换，而是继续在第i?1天收到ai?1的A币，第i?2天收到ai?2的A币，直到第j天收到aj的A币，再看情况决定是否兑换。

这个猜想可以用反证法得到证明，下面给出证明。 证明:

假设某个最优方案在[i,j)区间中，存在一个或多个兑换点，设最早的一个兑换点在第k天。

那么设从上次兑换点到第i?1天为止，共余下了x的A币，则：

情况一：x为非负数：那么显然到第k天的兑换点我们余下的钱将不会小于x，取消这个兑换点，将其并入后一个兑换点一起兑换，既提高了手中A币的价值，又省去了一次兑换手续费T。

情况二：x为负数：将这个兑换点提前至第i?1天，提前脱手了负数的A币，相应地可以使付出的B币减少，而且将区间[i,k]内的非负数归入下一 个兑换点，得到的收益不会比原来少。

综上两种情况，无论如何我们都可以通过调整将第k天的兑换点去掉，收入却没有减少或者更高，因此假设不成立，前面的猜想得到了证明。

这个猜想告诉我们，如果a[1]非负，我们不用急着兑换，而是等到第2天，

6

2006年全国信息学冬令营讲座

看a[1]?a[2]，如果还是非负，继续考虑第3天，第4天??，直到出现最小的i，满足a[1]?a[2]......?a[i]?0（如果找不到这样的i，则令i?n）。显然一定存在某个最优方案，使得第1到第i?1天均不是兑换点。因此，我们可以将序列

a[1],a[2]......a[i]压缩成一个数c[1]。类似地，我们继续从第i?1天考虑起，找到

一个最小的j，满足a[i?1]?a[i?2]......?a[j]?0（如果不存在，则令j?n）。同样的道理，第i?1到第j?1天均不是兑换点，我们可以继续将a[i?1],a[i?2]......a[j]压缩成一个数c[2]。依次类推，用同样的方法，可以将整个a序列压缩，变成一个长度为m(m??n)的序列c。c序列有个很重要的特征：除了最后一个元素可能非负外，其它所有元素为负数。因此，相应的sumc除了最后一个元素外，一定满足单调性。只要我们对最后一个元素做特殊处理，就可以完全套用前面的那个问题的方法来解决了。至此，我们成功地将原算法的时间复杂度降了一维！

二、 在非动态规划问题中的应用 对于一些非动态规划的问题，如果能够发现题中隐含的单调关系，同样可以运用一个类似的队列来实现时间上的“降维”。

【问题三】旅行问题（POI2004）

John打算驾驶一辆汽车周游一个环形公路。公路上总共有n车站，每站都有若干升汽油（有的站可能油量为零），每升油可以让汽车行驶一千米。John必须从某个车站出发，一直按顺时针（或逆时针）方向走遍所有的车站，并回到起点。在一开始的时候，汽车内油量为零，John每到一个车站就把该站所有的油都带上（起点站亦是如此），行驶过程中不能出现没有油的情况。 任务：

判断以每个车站为起点能否按条件成功周游一周。 输入：

第一行是一个整数n(3??n??1000000)，表示环形公路上的车站数。 接下来n行，每行两个整数。第i?1行含有：pi(0??pi??2000000000)，表示第i号车站的存油量；di(0?di??2000000000)，表示第i号车站到下一站的

7

2006年全国信息学冬令营讲座

距离。 输出：

输出共n行，如果从第i号车站出发，一直按顺时针（或逆时针）方向行驶，能够成功周游一圈，则在第i行输出TAK，否则输出NIE。 样例输入 5 3 1 1 2 5 2 0 1 5 4 样例输出 TAK NIE TAK NIE TAK

我们探讨一下本题的解决方法。 算法一：

最容易想到的方法是枚举所有车站作为起点，并且模拟汽车的行驶过程，看能否周游一圈，该方法的时间复杂度为O(n2)，就本题的规模而言，完全无法承受，优化势在必行！ 算法二：

简单的枚举法之所以低效，最根本的原因就在于，我们在依次判断各个车站作为起点能否可行的时候，没有充分利用前面得到的某些结果。

由于顺时针和逆时针行走，在本质上是一样的，因此我们暂且只考虑顺时针行走的情况。

原题中带有两个参量p和d，为了减少思考的复杂度，不妨将其压缩成一个。令a[i]?p[i]?d[i]，从第i站走到下一站，车内的汽油增加（或减少）了多少。

此外，为了方便讨论，我们将环拆开来，得到一个长度为2n?1的链

a[1],a[2].....an[a],n?[1]....a?n[ 2并满足：a[n?1]?a[1],a[n?2]?a[2]......a[2n?1]?a[n?1]

8

2006年全国信息学冬令营讲座

设suma[i]表示a序列中前i项的总和，即suma[i]??a[j]，特别的，有

j?1isuma[0]?0

此时，我们可以清楚地看到，要判断从某个车站i出发，能否成功地周游一圈，实际上就是看suma[i]?suma[i?1]，suma[i?1]?suma[i?1]，??

sum[a?i?1n]?su[m?这a1ni个数中是否存在负数，如果有负数，则表示中途一

定会出现没有油的情况，否则可以顺利行驶一周。

如果我们还是像最朴素的方法一样，通过循环来查找这n个数中是否存在负数，算法复杂度没有得到任何优化。但是我们注意到，如果n个数中的最小数非负，那么这n个数全部非负。求n个数中的最小数，很自然的让我们联想到了用堆来处理。用一个大小为n的堆保存suma[i]，suma[i?1]??suma[i?n?1]，判断suma[i]?suma[i?1]，suma[i?1]?suma[i?1]，??suma[i?n?1]?suma[i?1]中是否存在负数，实际上就是判断当前堆中的最小数是否小于suma[i?1]，可以用在枚举起始站的时候，随着i的增加，我们相应地要将suma[i]O(1)的复杂度实现。

从堆中删除，并将suma[i?n]插入堆中，删除插入的时间复杂度均为O(log2n)，因此整个算法的时间复杂度为O(nlog2n)。

这样，我们通过充分利用已经得到的结果，得到了一个比刚刚好得多的算法。但是本题的数据范围极大，O(nlog2n)的时间复杂度仍然不是特别理想，我们期望构造出更好的算法。

算法三：

受到算法二的启发，我们注意到，本题还可以是这样理解：

给定一个数列suma[1],suma[2],......,suma[2n?1]，以及n个区间

[L1R,1]L,R[2,2，每个区间L]n.?.R.?1..[,[L]2.ni,Ri]满足1??Li??n,Li?n?1?Ri。

要求你对于每个区间，给出suma[Li]...suma[Ri]中最小值的编号（如果存在多个这样的编号，任意输出一个即可）。

很明显，这个问题可以套用标准的的RMQ算法得到解决。这样算法的时间复

9

2006年全国信息学冬令营讲座

杂度就成功的降为了O(n)。问题到此似乎得到了完美解决，但是标准RMQ算法的编程复杂度很高，我们很自然地会期望得到一个更容易实现的高效算法。

注意一下这n个区间，发现它们的左右端点都是严格递增的！因此本题和一般的RMQ问题又存在着些许不同之处，或许利用区间的的单调性，可以像问题二一样得到一个高效且容易实现的算法。 算法四：

受到算法三的启发，我们尝试像例一一样，猜想n个最小值编号是满足单调性的。

其实只要再回过头去分析一下算法二的执行过程，注意到，如果某一次删去的suma[i]和插入的suma[i?n]都很大，对堆中的最小数是不够成影响的。顺着这个思路往下想，我们很惊喜地发现如下规律：

如果在某一段suma[i],suma[i?1]......suma[i?n?1]中，存在j?k，使得

suma[j]?suma[k]，那么suma[j]在以后的枚举中无论如何都不可能成为堆中最小的元素（因为suma[j]肯定要比suma[k]先删除出堆，而suma[j]又比suma[k]大），直到它被删除出堆。

这样刚刚的猜想得到了证明！其实真是因为保存过多对求解无意义的数据，直接导致了算法二的低效。 至此，我们发现此时的问题和问题一、二有着很大的相似性，因此我们完全可以采用类似的方法解决：

1．维护一个特殊的队列k，表示suma[k1],suma[k2]......suma[kn]有可能在今后的枚举中成为某一段的最小值。这个队列只能从队尾插入，但可以从两端删除，并且要满足k1?k2?k3......kn。

2．判断以i作为起点站前，若k1?i?1，直接将k1从队列中删除，接下来判断，若suma[kn]??suma[i?n?1]，则表示suma[kn]在今后不可能成为某一段的最小值，是多余的，将其从队列中删除，直到队列为空或suma[kn]?suma[i?n?1]，最后将i?n?1插入队列。

3．若suma[k1]??suma[i?1]，则表示以i作为起点的这一段中不会出现负数，标记从i出发，可以成功行驶一周。

判断每个i作为出发点可行的时间复杂度为O(1)，维护队列的时间复杂度为

10

2006年全国信息学冬令营讲座

O(N)，因此整个算法的时间复杂度为O(N)。这个算法的时空效率在理论上和

算法三差不多，不过实现难度要比算法三简单得多，甚至比用堆优化的算法二还要容易！

至此，本题得到了完美的解决！ 下面是对四个算法的比较： 算法一 算法二 算法三 算法四 空间复杂度 O(N) O(N) O(N) O(N) 时间复杂度 O(N^2) O(Nlog2N) O(N) O(N) 实现难度 很容易 简单 难 简单 三、总结： 本文的三个例子，都是通过充分挖掘问题当中隐含的单调关系，运用特殊的 队列，成功地实现的算法的优化。而且由于采用的数据结构简单，优化过后的编程难度在最初算法的基础上几乎没有增加多少。由此可见，有时候要构造出一个优秀的算法，不一定非得运用多么高深的数据结构。通过不断挖掘问题的隐含条件，也许较简单的数据结构就能够胜任算法的优化！

当然，在竞赛当中，通过寻找隐含数据关系，灵活运用数据结构的问题远不 止文中提到的这些类型，有的问题思考、处理起来都要难得多。但是只要我们善于发现，勇于创新，就能够构造出更加完美的算法。

【感谢】 衷心感谢曹利国老师在写这篇论文时给我的指导和帮助。 衷心感谢周戈林同学给我的帮助。

【参考文献】

《算法艺术与信息学竞赛》——刘汝佳、黄亮，清华大学出版社 2005年信息学国家集训队队员周源的论文

11

本文来源：https://www.bwwdw.com/article/51rh.html