| ||||||||||
Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
平衡二叉树做的,花了三天本题关键是,插入时如果格子被占领,得快速找到这个位置右边最近的空格。 然后插入位置到空格间的所有数字做整体平移。 我是用二叉树做的。 每个结点记录自己相对父节点的偏移起末点量,以及插入的数据量。 插入时最复杂的一种情况是往左结点插入,左结点溢出波及到右结点。 这时得根据右结点是否满了,右结点的左结点是否满了等分情况递归处理。 另一个需要考虑的是树的平衡性。 我借鉴了平衡二叉树的策略,左右高度差大于1就调整。 虽然调整次数过于频繁,但实现简单些,就这样吧。 Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator