原题地址
本沙茶去年曾经用双线段树的方法捉了这题(详见这里),最近重新审视这题发现,借助平衡树,可以得到更简单的方法。

题目大意:
有一个长度为N的内存条,每个位置的状态有占用和不占用两种,有4种操作:
(1)Reset:清空所有内存(即将所有位置的状态改为不占用,删除所有内存块);
(2)New x:申请一个新的内存块,即找到一个长度为x的连续不占用位置区间,将它们标记为占用,若有多个这样的区间,取最左边的,若木有输出Reject New;
(3)Free x:在已申请的内存块中,找到包含位置x的并释放(将该内存块删除,同时其占用的所有位置改为不占用),若木有内存块包含位置x,则输出Reject Free;
(4)Get x:找出已申请的内存块中,左起第x个,并输出其左端点;若已申请的内存块数目不足x个,则输出Reject Get。

可以发现,每个已经申请的内存块尽管代表一段区间,但仍然是独立的单位,因此,可以把内存块当成结点,用平衡树维护(关键字为内存块的左端点位置),New操作中内存块的插入与Free操作中内存块的删除均在此平衡树内进行,Reset操作只需要将整棵树销毁即可。
问题是,在New操作中,需要找到一个长度为x的连续不占用区间,而连续的不占用区间并不是独立的单位,因此需要使用线段树维护。在线段树中,需要维护<1>结点区间内最长连续不占用块的长度;<2>结点区间左端、右端连续不占用块的长度(否则无法维护<1>);同时,由于在New操作中需要区间整体改占用,Free操作中又需要区间整体改不占用,所以应当支持整体改值的标记,对于Reset操作,只需要全部位置改不占用即可(不能重新建树!!);

这样,利用一棵平衡树加一棵线段树,就可以得到一个很简单的方法了(代码量是双平衡树或双线段树的一半左右);

这题的启示是,在解决数据结构统计类题的时候,到底选用什么样的数据结构,是有讲究的,因为它将直接影响到编程复杂度。一般来说,线段树比平衡树好写,但是对本题而言,双线段树反而不如平衡树加线段树好写,这是因为对于内存块使用平衡树维护比使用线段树维护更好。在以后做这种题的时候,要多想一下,找到简便方法。

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理