2006年全国信息学冬令营讲座
由于在行尾有一个哨兵h(x,n+1)=-1，所以最终栈中非哨兵元素会被全部弹出，从而不会遗漏任何一个值。
算法的伪代码如下：
maxarea=0;
for (x=1; x<=m; x++)
{
计算h(x,i)，设哨兵h(x,n+1)=-1;
设栈指针为0；
for (i=1; i<=n+1; i++)
{
(设栈顶元素为A，对应列坐标为j)
if ((栈为空) or (h(x,i)>A))
插入h(x,i); continue;
if (h(x,i)=A)
continue;
while (h(x,i) { area=A*(i-j); if (area>maxarea) then maxarea=area; 从栈中删除A； } if (A==h(x,i)) continue; 设最后删除的元素为C，对应列坐标为j 插入元素h(x,i)，列坐标设为j } } 算法1 这个算法的时间复杂度是O(MN)，空间复杂度可以用滚动数组降为O(N)，是一个十分优秀的算法。从解题过程中可以看出，基本数据结构之一的栈发挥了很重要的作用。整个算法都是围绕栈展开的。但是，与普通的栈不同，这个算法中的栈需要考虑到元素之间的大小关系，还要记录相应列坐标的值。可以很容易证明，算法1中的栈任何时候都满足从栈底到栈顶的元素组成一个严格递增的序列。这便是与一般的栈的不同之处。 通过巧妙地利用与改造栈，我们成功地解决了这道例题。下面将通过例2来体现另一种重要的基本数据结构——线性表的应用。 第9页 共29页 2006年全国信息学冬令营讲座 二、线性表的应用 营业额统计2 给定N（1≤N≤32767）天的营业额a1,a2,a3,??an. 定义最小波动值： 该天的最小波动值=min{|该天以前某一天的营业额-该天营业额|}. 特别地，第一天的最小波动值即为a1. 试求N天的最小波动值之和。 分析： 这道题目的规模很大，如果简单地用两层循环解决，时间复杂度高达O(N2)，难以在时限内出解。算法低效的原因在于没有高效地将数据组织起来，而是松散地存储在数组中，导致对于每一个营业额都需要检查前面所有的营业额。实际上，有一种高级数据结构——平衡树3可以解决这个问题。如图12所示，我们可以在将一天的营业额插入平衡树的过程中得到该天的最小波动值。方法是求出所有在插入路径上的数字与改天营业额差的绝对值，从中取出最小值（如图中取min{|5-7|,|8-7|,|6-7|}=1）。 插入 7 5 3 8 6 1 9 7 插入后的位置 图12 这样，应用平衡树可以在O(Nlog2N)时间内得到问题的解。 然而，尽管平衡树十分高效，但是它的编程复杂度却非常高。各种左旋、右旋甚至双旋都比较复杂，稍不注意就可能出错，导致整个程序的失败。这使得我们在紧张的信息学比赛中必须谨慎使用这样“高效+高出错率”的数据结构。那么，基本数据结构能否在这里得到应用呢？是的。 首先，将这N个元素进行排序，同时记录下原来第i个元素在排序后的位置bi. 接着，将排序后的序列建成一个双向链表。然后，按照从an到a1的顺序依次处理每个元素。对于an，由于知道它在排序后的序列中的位置bn，可以查看bn的前驱pre[bn]与后继next[bn]所指的数。很显然，由于数据在双向链表中是有序的，所以最小波动值必然是an与这两个数中的某一个的差的绝对值。当然，如果前驱或后继为空，就不需要考虑相应的位置了。处理完an后，我们把它从双向链表中删除（由前文可知，这一步操作的时间复杂度仅为O(1)），接着处理an-1. 这样，每当处理ai时，ai+1，例2 23 湖南省2002年省队选拔赛试题 平衡树本质上是一棵二叉排序树，但是它的各项基本操作（如取最值、插入、删除等）的时间复杂度为O(log2N)或平摊为O(log2N). 关于平衡树的介绍详见参考书目[2]. 第10页 共29页 2006年全国信息学冬令营讲座 ai+2，??， an已被从双向链表中删除，而此时bi的前驱与后继所指的数就等于将a1，a2，??， ai排序后ai的前驱与后继。整个算法分为排序，建表与处理三部分。很显然，建表与处理的时间复杂度均为O(N)，所以此算法的时间复杂度与排序的时间复杂度同阶，为O(Nlog2N). 图13为对一组数据处理的图示。 原数据：a1=9 a2=3 a3=8 排序后：3,8,9 b1=3 b2=1 b3=2 双向链表 3 8 9 处理a3：b3=2，前驱为1，后继为3，最小波动值为min{|8-3|,|8-9|}=1 删除a3后： 3 9 处理a2：b2=1，无前驱，后继为3，最小波动值为min{|9-3|}=6 删除a2后： 9 处理a1：根据定义，最小波动值即为9 图13 相应的伪代码： 1、输入N，a1，a2，a3，??，an 2、将a1，a2，a3，??，an按照从小到大的顺序排序，得到序列c1，c2，c3，??， cn，并记录下每个ai在新序列中的位置bi 3、在新的序列上建立双向链表 4、按照从an到a1的顺序依次处理每个元素： result=0; for (i=n; i>=2; i--) { result+=min{|ai-cpre[bi]|,|ai- cnext[bi]|}; （如果pre[bi]=0或next[bi]=0则不予考虑） } result+=a1; 5、输出result 算法2 在 本题中，平衡树可以高效地得出答案，但是由于其很高的编程复杂度，导致我们在 第11页 共29页 2006年全国信息学冬令营讲座 比赛中难以保证程序的正确性。而之后运用双向链表的方法十分简洁，既没有增加算法的时间复杂度，又大大降低了编程复杂度，实为比赛时的首选，并且其清晰的思路与独到的见解也值得学习与推广。 以上通过两道例题简单介绍了两种基本数据结构——栈与线性表的应用。下文中的例3将展示另一种基本数据结构——队列的应用。 三、队列的应用 例3 瑰丽华尔兹4 给定一个N行M列的矩阵，矩阵中的某些方格上有障碍物。有一个人从矩阵中的某个方格开始滑行。每次滑行都是向一个方向最多连续前进c格（也可以原地不动）（两次滑行的c值不一定相同）。但是这个人在滑行中不能碰到障碍物。现按顺序给出K次滑行的方向（东、南、西、北中的一个）以及对应的c，试求这个人能够滑行的最长距离（即格子数）。 数据范围：1≤N,M≤200，K≤200， ?ci?1ki≤40000 分析： 本题是一个求最值的问题。根据题目中K次滑行的有序性以及数据范围，可以很容易设计出这样一种动态规划算法： 令f(k,x,y)=此人k次滑行后到达(x,y)方格时已经滑行的最长距离。动态规划的状态转移方程如下（以下仅给出向东滑行的状态转移方程，其他3个方向上的转移方程可以类似地推出）： f(0,startx,starty)=0 f(k,x,y)=max{f(k-1,x,y),f(k-1,x,y-1)+1,f(k-1,x,y-2)+2,??,f(k-1,x,y’)+y-y’} （其中y’为满足y=1或(x,y’-1)上有障碍或y’=y-ck的最大值） 从图14中可以很清楚地看出动态规划转移的条件： 令ck=2，仅举一行为例： 其中，黑色方格表示障碍，每个箭头表示发出箭头的状态可以去改进被箭头指向 的状态（当然，这两个状态的k值相差1）。 图14 现在来分析这个动态规划算法的时间复杂度。 显然，状态总数为O(KMN)，而每次状态转移在最坏情况下的时间复杂度为O(max{M,N})，因此总的时间复杂度为O(KMN*max{M,N})=O(1.6*109)，难以承受。因 4 NOI2005 Day1 adv1900 第12页 共29页
