全部博文（330）
分类：
2011-03-19 10:22:18
因为忙，不少计划写下来的东西都一直搁置着。其中一个拖了很久都没写的就是 UyHiP 一月的题目 了。这是一道看上去非常困难的算法题目，当时我没能解答出来；看到答案后才恍然大悟，拍案叫绝。这是一道非常少见的算法好题，在这里记下来。
一个国家里有 N 个公民，这些公民从 1 到 N 依次编号。这是一个民主国家，国家做出的每个决定都需要全体公民投票，每个人必须且只能投一票。
不过，随着该国家人口数量的增加，这种投票方式的效率越来越低。于是，这个国家实行了一种新的民主制度。每过四年，这个国家将会举行一次“代表选举大会”，届时，每个公民都必须且只能提名一个他信得过的人，来作为他自己的代表。注意，提名自己作为自己的代表也是允许的。对于每个被提名了的人，有百分之多少的人提名他，他就拥有了相当于多少张选票的权力（向下取整）。在接下来的四年里，国家要做出某项决定时，就只需要这些代表来参加了。
比方说，这个国家有 200 个人，在代表选举大会上，有 98 个人提名 1 号公民当代表，有 101 个人提名 2 号公民当代表，有 1 个人提名 200 号公民当代表。结果就是，只有 1 号公民和 2 号公民成为代表，在接下来的四年里参与投票，其中 1 号公民一票当 49 票，2 号公民一票当 50 票。值得注意的是， 200 号公民虽然有提名，但支持率仅 0.5% ，因此他今后四年没有当代表的权力。
为了支持新的民主政策，你需要设计一套算法，来计算每届代表选举大会结束后，哪些公民成为了代表，他们手中各自有多少票的权力。程序的输入数据来源于一盘磁带。磁带上有 N 个数，分别记录了这 N 个公民各自提名的代表的编号（由于提名是匿名的，磁带上的数据不是顺序的，你无法判断出每个数都是谁的）。程序可以多次读取磁带，但是每次都只能是从头到尾依次读取每一个数。由于这个国家的人数已经增加到了一定规模，因此你的程序必须非常高效。具体地说，你的算法必须要满足以下几点限制：
1. 你的程序读取磁带的次数要尽可能的少；
2. 磁带是只读的；
3. 程序可以在自己的内存里储存变量，不过只能使用 O(1) 个单元的空间（即所耗费的内存空间与 N 无关）；
4. 内存里每个单元的空间只能储存 0 到 N 之间的整数（包括 0 和 N ）；
5. 预处理阶段完成后，程序将进入询问阶段，即针对形如“公民 x 获得了多少票的权力”的问题给出回答。一旦预处理完成进入询问阶段后，程序就不能再接触磁带了。
现在的问题是，在最坏情况下，最少需要读取多少次磁带？给出一个满足要求的算法，并证明读取磁带的次数已经不能再少了。
”
看到这里我就突然想起了拼音输入法。最基本的拼音输入法也就是查询词库，要求跟上面的基本相同：读硬盘词库次数尽可能少，词库只读，耗费空间要少，查询要快。除此之外，拼音输入法还要求能够把相同拼音的字或词按照出现频率排序，不断完善升级的词库，包容用户自己建立的词库，词库的词频不断更新；很少人工干预下解决多音字问题（方法就是把多音字的每个音都组成词，没想到好方法），智能整句，智能邻接词（智能我一点思路都没有）。
抛开输入法，这个问题我想到的一个不符合要求但站得住脚的方法（要求N的大小可以被内存顶住）：从磁带读一次，占用的N个空间分别存储这N个公民的选票，根据磁带上面的数据给相应的空间做+1运算。查询时相应空间除以N并向下取整。这个方法空间占用是O(N)，但查询速度是O(1)。看完matrix67的解析，我发现他的算法无法使用到拼音输入法，而只能用于选票，我的想法也许可以，思路就暂时打住。
下面是matrix67给的答案：
“
答案：最少需要读取两次磁带。
首先我们来说明，读取一次磁带是不够的。假设 N 是 100 的某个很大的倍数。磁带前面有 (N/2) + 50 个互不相同的数。磁带后面则又是 50 个不同的数，其中每个数都出现了 (N/100) - 1 次，从而恰好填充满整个磁带。注意，出现了 (N/100) - 1 次就意味着，再多出现一次就能成为代表了。因此正确的输出结果就是，如果这 50 个人中有人正好也在磁带前半部分出现过，则他将获得一票的代表权力。因此，如果程序想要一次读带就完成任务，在读完前 (N/2) + 50 个数之后，它必须要能记住哪些数出现过哪些数没出现过，这显然无法用 O(1) 的空间存下。这就说明，仅用一次磁带是不够的。
如果允许读磁带两次，我们有下面这个算法。
首先，通读一遍磁带，同时维护一个“谁谁谁目前都得到了多少次提名”的表（没有被提名的人就不用写进表里了）。为了保证内存空间在常数级别，我们引入“裁减”操作：只要表里的人数达到 100，就让所有代表都减少一个提名。这样的话，必然有人又会变成“零提名”，从而让表里的人数回到 100 以下。每当表里的人数达到 100 时，我们都进行一次裁减操作，除非我们正好处理完最后一个提名。
现在我们证明，最后没有留在表中的人，都绝不可能成为代表。反证，假设某人得到了 x ≥ N/100 次提名，但最后却没有留在表中。由于一次裁减只能让他失去一个提名，因此读取磁带的过程中至少发生了 x 次裁减。每次裁减都会裁掉 100 个提名，因此整个过程中至少有 100x 个提名被裁掉了。但我们一共就只有 N 个提名，而且最后一个提名是肯定不会被裁掉的，因此 100x 必然严格地小于 N 。这与 x ≥ N/100 矛盾。因此，所有有可能成为代表的人都已经留在表里了。
接下来就容易了。再从头至尾读一遍磁带，并且记录每个代表真正的提名次数。只不过这一次，我们只为上一轮最后还留在表里的那些人做记录。第二轮磁带读完后，我们便能算出每个代表拥有的权力了。
”
