《国家集训队1999论文集 陈宏》由会员分享，可在线阅读，更多相关《国家集训队1999论文集 陈宏（15页珍藏版）》请在金锄头文库上搜索。
1、IOI99 中国集训队优秀论文选 - 21 -数据结构的选择与算法效率从 IOI98 试题 PICTURE 谈起福建师大附中 陈宏【关键字】数据结构的选择 线性结构 树形结构【摘要】算法 + 数据结构=程序。设计算法与选择合适的数据结构是程序设计中相辅相成的两方面，缺一不可。数据结构的选择一直是程序设计中的重点、难点，正确地应用数据结构，往往能带来意想不到的效果。反之，如果忽视了数据结构的重要性，对某些问题有时就得不到满意的解答。通过对 IOI98 试题Picture 的深入讨论，我们可以看到两种不同的数据结构在解题中的应用，以及由此得到的不同的算法效率。本文以Picture 问题为例，探讨数
2、据结构的选择对算法效率的影响。【正文】引言算法通常是决定程序效率的关键，但一切算法最终都要在相应的数据结构上实现，许多算法的精髓就是在于选择了合适的数据结构作为基础。在程序设计中，不但要注重算法设计，也要正确地选择数据结构，这样往往能够事半功倍。在算法时间与空间效率的两方面，着重分析时间效率，即算法的时间复杂度，因为我们总是希望程序在较短的时间内给出我们所希望的输出。如果在空间上过于“吝啬”而使得时间上无法承受，对解题并无益处。本文对 IOI98 的试题 Picture 作一些分析，通过两种不同数据结构的选择，将了解到数据结构对算法本身及算法效率的影响。Picture 问题及算法设计一、Pic
3、ture 问题Picture 问题是 IOI98 的一道试题，描述如下：墙上贴着一些海报、照片等矩形，所有的边都为垂直或水平。每个矩形可以被其它矩形部分或完全遮盖，所有矩形合并成区域的边界周长称为轮廓周长。例如图 1 的三个矩形轮廓周长为 30：数据结构的选择与算法效率从 IOI98 试题 PICTURE 谈起- 22 - IOI99 中国集训队优秀论文选图 1要求编写程序计算轮廓周长。数据量限制：0矩形数目 1)的一般区间。一般情况下，线段树的结点类型定义如下：TypeLines_Tree = Objecti, j : integer; 结点表示的区间的顶点标号 I, Jcount : in
4、teger; 覆盖这一结点的区间数leftchild, rightchild : Lines_Tree; 二叉树的两个子结点 end关于 Lines_Tree 的其它数据域与定义的运算将陆续添加。图 8 是一棵线段树，描述的区间端点可以有 10 种取值。其中记录着一个区间3，6，它用红色的3， 5及5，6的并采表示。图中红色结点的 count 域值为 1，黑色结点的count 域值为 0。1,101,5 5,101,3 3,5 5,7 7,101,2 2,3 3,4 4,5 5,6 6,7 7,8 8,108,9 9,10图 8直观地看，子结点就是父结点区间平均分成两部分。设 L, R 是父结
5、点的区间端点，我们可以增加 Lines_Tree.Build(l, r : integer)递归地定义线段树如下:Procedure Lines_tree.Build(l, r : integer)1 I l 左端点2 J r 右端点3 Count 0 初始化4 If r - l 1 是否需要生成子结点，若 r-l=1 则是初等区间5 then k (l + r) 平均分为两部分6 new(leftchild)数据结构的选择与算法效率从 IOI98 试题 PICTURE 谈起- 30 - IOI99 中国集训队优秀论文选7 leftchild.Build(l, k) 建立左子树8 new(ri
6、ghtchild)9 rightchild .Build(k, r) 建立右子树10 else leftchild nil11 rightchild nil设根结点是 Root，建树需要执行 Root.Build。由递归定义看出，线段树是一棵平衡树，高度为 logN 。建立整棵树需要的时间为 O(N)。以上着重说明了线段树的存储原理，我们还应建立线段树的基本运算。线段树可以存储多个区间，所以支持区间插入运算 Lines_Tree.Insert(l, r : integer)，定义如下：Procedure Lines_Tree.Insert(l, r : integer) l, r是待插入区间，
7、l、r 都是原始顶点坐标1 if (l a(i + j) div 2 是否能覆盖到右孩子结点区间 6 then rightchild.Insert(l, r) 向右孩子插入类似地，线段树支持区间的删除 Lines_Tree.Delete(l, r : integer)，定义如下：Procedure Lines_Tree.Delete(l, r : integer) l, r是待删除区间，l、r 都是原始顶点坐标1 if (l a(i + j) div 2 是否能覆盖到右孩子结点区间 6 then rightchild.Delete(l, r) 向右孩子删除执行 Lines_Tree.Delet
8、e(l, r : integer) 的先决条件是区间l, r曾被插入且还未删除。如果建树后插入区间2，5而删除区间3，4是非法的。通过分析插入与删除的路径，可知 Lines_Tree.Insert 与 Lines_Tree.Delete 的时间复杂度均为 O(logN)。 (详见 附录 1)由于线段树给每一个区间都分配了结点，利用线段树可以求区间并后的测度与区间并后的连续段数。(一)、 测度由于线段树结构递归定义，其测度也可以递归定义。增加数据域 Lines_Tree.M表示以该结点为根的子树的测度。M 取值如下：aj ai 该结点 Count0M = 0 该结点为叶结点且 Count=0Le
9、ftchild.M + Rightchild.M 该结点为内部结点且 Count=0数据结构的选择与算法效率从 IOI98 试题 PICTURE 谈起IOI99 中国集训队优秀论文选 - 31 -据此，可以用 Lines_Tree.UpData 来动态地维护 Lines_Tree.M。UpData 在每一次执行 Insert 或 Delete 之后执行。定义如下：Procedure Lines_Tree.UpData1 if count 0 2 then M aj i 盖满区间，测度为 aj ai3 else if j - i = 1 是否叶结点 4 then M 0 该结点是叶结点5 els
10、e M Leftchild.M + Rightchild.M内部结点UpData 的复杂度为 O(1)，则用 UpData 来动态维护测度后执行根结点的Insert 与 Delete 的复杂度仍为 O(logN)。(二)、 连续段数这里的连续段数指的是区间的并可以分解为多少个独立的区间。如1，22，35，6 可以分解为两个区间1，3 与5， 6，则连续段数为 2。增加一个数据域 Lines_Tree.line 表示该结点的连续段数。Line 的讨论比较复杂，内部结点不能简单地将左右孩子的 Line 相加。所以再增加 Lines_Tree.lbd 与Lines_Tree.rbd 域。定义如下：1
11、 左端点 I 被描述区间盖到lbd = 0 左端点 I 不被描述区间盖到1 右端点 J 被描述区间盖到rbd = 0 右端点 J 不被描述区间盖到lbd 与 rbd 的实现：1 该结点 count 0lbd = 0 该结点是叶结点且 count = 0leftchild.lbd 该结点是内部结点且 Count=01 该结点 count 0rbd = 0 该结点是叶结点且 count = 0rightchild.rbd 该结点是内部结点且 Count=0有了 lbd 与 rbd，Line 域就可以定义了：1 该结点 count 0Line = 0 该结点是叶结点且 count = 0Leftch
12、ild.Line + Rightchild.Line - 1 当 该 结 点 是 内 部 结 点 且 Count=0， Leftchild .rbd = 1 且 Rightchild .lbd = 1Leftchild.Line + Rightchild.Line 当 该 结 点 是 内 部 结 点 且 Count=0， Leftchild .rbd 与 Rightchild .lbd 不 都 为 1据此，可以定义 UpData动态地维护 Line 域。与 UpData 相似，UpData也在每一次执行 Insert 或 Delete 后执行。定义如下：Procedure Lines_Tree
13、.UpData1 if count 0 是否盖满结点表示的区间数据结构的选择与算法效率从 IOI98 试题 PICTURE 谈起- 32 - IOI99 中国集训队优秀论文选2 then lbd 13 rbd 14 Line 15 else if j - i = 1 是否为叶结点 6 then lbd 0 进行到这一步，如果为叶结点，count = 07 rbd 08 line 09 else line Leftchild.line + Rightchild.line - Leftchild.rbd * Rightchild .lbd 用乘法确定 Leftchild.rbd 与 Rightch
14、ild.lbd 是否同时为 1同时，由于增加了 Line、 M 等几个数据域，在建树 Lines_Tree.Build 时要将新增的域初始化。至此，线段树构造完毕，完整的线段树定义如下：Lines_Tree = objecti, j : integer;count : integer;line : integer;lbd, rbd : byte;m : integer;leftchild,rightchild : Lines_tree;procedure Build(l, r : integer);procedure Insert(l, r : integer);procedure Delete(l, r : integer);procedure UpData;procedure UpData;end有了线段树这个工具
