Beyond the Void

从描述中看出，非前缀且权值和最小，于是我想到了哈夫曼编码。类似的，对于这道题，我们可以考虑建立一个k叉树，这个树的每个叶节点代表一个字符串，只须找出最小的n个叶节点的权值，就是结果。

首先建立一个0节点，在此基础上首先加入每个单个字母，当叶节点的个数不足n个时，取出最小的一个节点，对这个节点进行扩展，即把它的权值分别加上每个字母的权值，作为新的k个叶节点。否则把前n小的节点取出，计算它们的权值之和。如果这个和小于当前已知最优解，更新最优解，否则结束，因为再扩展一定不会比当前值小。

实际上我们并不需要建立树结构，只需要对叶节点的权值抽象的维护。首先把每个字母的权值插入优先队列，每次取出前n小的值计算，并以最小值来维护。

一般情况下我们用最小堆实现优先队列，但是堆中可能会存在n^2个元素，大大超过了空间限制。但是优先队列中只有前n小的元素是对我们有用的，我们可以以此改进堆，只存储前n小的元素。当插入一个新的元素时，把堆中的最大值删除，这样维护的一定是前n小的。这样又会带来新的问题，在最小堆中取最大值是O(n)时间复杂度的。于是必须同时维护一个最大堆，使取删最大值变为O(logn)。需要同时维护两个堆，在每个元素之间建立映射关系，每次删除都要对两个堆进行维护。

这样虽然可以解决问题，但是会大大增加编程的复杂度，可以考虑不用堆来维护。我用了更强大的数据结构，平衡树。平衡树在插入、取最大、取最小、删除上均有O(logn)的时间复杂度，使用平衡树可以使编程思路更清晰。我用的是Treap。

以下是我用Treap实现的代码。

Read the rest of this entry »

排序二叉树能解决好多问题，除了基本的插入、删除、遍历、查找键值以外，还有查找第K小（大）的数的操作。看了一天程序，总算明白了，其实本质和二分查找相似。

从根节点开始查找第r小的数，如果r<=(k的左子树节点的总个数)，那么第r小的节点一定在k的左子树，在k的左子树继续查找第r小的节点。
如果r>(k的左子树节点的总个数+节点k的重复单元个数)，那么第r小的节点一定在k的右子树，在k的右子树继续查找第r-(k的左子树节点的总个数+节点k的重复单元个数)小的节点。
如果以上都不满足，那么k就是第r小的数，返回k的键值。

（其实我很不习惯用静态数据存储二叉树，但考虑到效率和iRachex大牛的建议，还是使用了静态存储）

查找以k为根的树中，第r小的节点的值：

int find(int k,int r)
{
if (r<=p[p[k].l].size)
return find(p[k].l,r);
else if (r> p[p[k].l].size+p[k].cnt)
return find(p[k].r,r-(p[p[k].l].size+p[k].cnt));
return p[k].key;
}

NOI在即，我还不会Treap，这是一件多么恐怖的事情啊。今天下午在iRachex大牛的指导下，我学了Treap。不能算是会了，只是初窥门径而已。

开始看了许多介绍文章，还被误导了。因为有人用最大堆，有人用最小堆，我被迷惑了。还有就是左旋和右旋，有的人正好认识相反，我恰好看着两篇认识相反的文章在学习。

总结一下Treap

插入：
按BST基本性质插入，生成修正值(有人叫优先级、附加值、堆权值)，并按照最大堆序维护修正码。
向左子树插入返回后
如果左子修正值大于根修正值，堆序被破坏，将根旋转到右子树（右旋）
向右子树插入返回后
如果右子修正值大于根修正值，堆序被破坏，将根旋转到左子树（左旋）

删除：
叶节点：直接删除
链节点：链接上子节点并删除
完全节点：
若其左子树修正值较小，将该节点左旋，递归删除左节点
若其右子树修正值较小，将该节点左旋，递归删除右节点

左旋：将根X旋转到左子树

Y=X右子
X右子=Y左子
Y左子=X
X=Y

右旋：将根X旋转到右子树

Y=X左子
X左子=Y右子
Y右子=X
X=Y

一个非常棒的Treap演示
http://www.ibr.cs.tu-bs.de/courses/ss98/audii/applets/BST/Treap-Example.htm

附一段第一次写的Treap代码
#include
#include
#define MAX 100

int i;
for (i=3;i>=1;i--)
T.insert(T.root,i);
T.print(T.root);
for (i=3;i>=1;i--)
{
cout << endl;
T.remove(T.root,i);
T.print(T.root);
}
return 0;
}