因为忙，不少计划写下来的东西都一直搁置着。其中一个拖了很久都没写的就是 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 是 100 的某个很大的倍数。磁带前面有 (N/2) + 50 个互不相同的数。磁带后面则又是 50 个不同的数，其中每个数都出现了 (N/100) - 1 次，从而恰好填充满整个磁带。注意，出现了 (N/100) - 1 次就意味着，再多出现一次就能成为代表了。因此正确的输出结果就是，如果这 50 个人中有人正好也在磁带前半部分出现过，则他将获得一票的代表权力。因此，如果程序想要一次读带就完成任务，在读完前 (N/2) + 50 个数之后，它必须要能记住哪些数出现过哪些数没出现过。这需要 O(log(n)) 的空间来完成。但算法只能用 O(1) 的空间。这就说明，仅用一次磁带是不够的。

     如果允许读磁带两次，我们有下面这个算法。

     首先，通读一遍磁带，同时维护一个“谁谁谁目前都得到了多少次提名”的表(没有被提名的人就不用写进表里了)。为了保证内存空间在常数级别，我们引入“裁减”操作：只要表里的人数达到 100，就让所有代表都减少一次提名。这样的话，必然有人又会变成“零提名”，从而让表里的人数回到 100 以下。每当表里的人数达到 100，我们都进行一次裁减操作，但统计磁带中的最后一个提名时除外。

     现在我们证明，最后没有留在表中的人，都绝不可能成为代表。反证，假设某人得到了 x ≥ N/100 次提名，但最后却没有留在表中。由于一次裁减只能让他失去一个提名，因此读取磁带的过程中至少发生了 x 次裁减。每次裁减都会裁掉 100 个提名，因此整个过程中至少有 100x 个提名被裁掉了。但 100x ≥ N，这显然是不可能的――我们一共就只有 N 个提名，而且最后一个提名是肯定不会被裁掉的，因此被裁掉的提名数不可能等于 N(当然更不可能大于 N 了)。因此，所有有可能成为代表的人都已经留在表里了。

     接下来就容易了。再从头至尾读一遍磁带，并且记录每个代表真正的提名次数。只不过这一次，我们只为上一轮读完磁带后还留在表里的那些人做记录。这样便能算出每个代表拥有的权力了。

建议继续学习：

1. 趣题：2n位平衡01串平均有多少个平衡前缀？    (阅读：2516)
2. UyHiP趣题：拉灯游戏总有解吗？    (阅读：1739)
3. UyHiP趣题：如果每个人都随大流，结果会怎样？    (阅读：1609)
4. UyHiP趣题：按照盒子的三边长之和来计费有没有漏洞？    (阅读：1620)