1、题目要求：
在一个论坛中，有一个用户，他的发帖量在总帖数中占了一半以上，并且在每一个帖子下都有他的回复，人们管他叫水王
用最简单、快速的方法找到这个水王
2、实现思路：
在一个列表中，找到一个出现次数最高的发帖人，发帖数量占总帖数的一半以上！
可以的方法很多，甚至可以统计每一个用户的发帖量，进行查找最大的那个（当然这只是第一想法，肯定不是最快也不是最简便的）
在老师的提示下，想到了这么一个方法，两两消除不同的 id号，最终剩下的就是那个水王
根据一个基本假设（假设n为总数，m 为水王发帖数，占到了一半以上）
m/n > 1/2
那么，当消除的都不是水王时，分母减小，分数值增大 m/(n-2) > 1/2依旧是成立的；
当消除了的是一个水王和非水王时，(m-1)/(n-1)>1/2 成立，(m-1)/(n-1-1)>1/2依然成立。
即水王帖数仍然在一半以上！所以这个方法是等效的，符合要求。消到最后，都剩下相同的了，就是水王。
3、思路整理（实现步骤）：
不需要真正对列表进行删除相消（前提：这个列表中必须有一个符合条件的水王）
①将第一个id 假设为king，king比其他id多出现频数num设为1
②将第二个id 与当前king比较，不同的话，将原来king的num值减 1，
若num为0了，直接跳过这个id，将下一个id作为king；若num不为0，king依然为当前king
③若相同的话，原来的num加一，说明，又多出了一个king id
循环②和③，直到最后一个数，king值就是水王的id
4、源代码：
1 //找水王（在一个论坛中，发帖数超过总帖数的一半的那个id号） 2 //王永维，2016，05，18 3 #include<iostream> 4 #include<string> 5 #define N 10 //可以定义列表长度 6 7 using namespace std; 8 int main() 9 { 10 string king; 11 //定义列表 12 string IdList[N]={"2水货","3潜水员","1水王","3潜水员","1水王","1水王","1水王","1水王","2水货","3潜水员"};
13 //string IdList[N]={"2水货","3潜水员","1水王","3潜水员","1水王","1水王","1水王","1水王","2水货","3潜水员","2水货","3潜水员","1水王","3潜水员","1水王","1水王","1水王","1水王","2水货","3潜水员"}; 14 //string IdList[N]={"2水货","2水货","3潜水员","2水货","3潜水员","1水王","3潜水员","1水王","1水王","1水王","1水王","2水货","3潜水员","2水货","3潜水员","1水王","3潜水员","1水王","1水王","1水王","1水王","3潜水员","1水王","3潜水员","1水王","1水王","1水王","1水王","2水货","3潜水员"}; 15 //string IdList[N]={"oottt","eee","ott","oottt","oottt","oottt","oottt","oottt","tt55","oottt"}; 16 //string IdList[N]={"1","2","3","1","1","1","1","2","5","1"};
17 //假设第一个id是水王 18 int i=0; 19 int num=1; 20 king=IdList[0]; 21 for(i=1;i<N;i++) 22 { 23 //如果当前id和king id不同 24 if(IdList[i]!=king) 25 { 26 //num-1 27 num=num-1; 28 //num为0，将下一个id 设为 king，并直接跳过下一次循环,并将 num设为1 29 //若num不为0，king 不变 30 if(num==0) 31 { 32 king=IdList[i+1]; 33 i=i+1; 34 num=1; 35 } 36 } 37 //若id和king id相同，num+1 38 else 39 { 40 king=IdList[i]; 41 num=num+1; 42 } 43 } 44 cout<<"要找的水王的 id 为:"<<king<<endl; 45 return 0; 46 }
5、运行结果：
①测试文字列表string IdList[10]={"2水货","3潜水员","1水王","3潜水员","1水王","1水王","1水王","1水王","2水货","3潜水员"};
②测试更长的列表string IdList[30]={"2水货","2水货","3潜水员","2水货","3潜水员","1水王","3潜水员","1水王","1水王","1水王","1水王","2水货","3潜水员","2水货","3潜水员","1水王","3潜水员","1水王","1水王","1水王","1水王","3潜水员","1水王","3潜水员","1水王","1水王","1水王","1水王","2水货","3潜水员"};
③测试数字和普通字符串
string IdList[10]={"oottt","eee","ott","oottt","oottt","oottt","oottt","oottt","tt55","oottt"};
string IdList[10]={"1","2","3","1","1","1","1","2","5","1"};
6、总结分析：
这次的问题比较简单，实现起来不是很难，但方法的好坏决定了这个程序的运算时间和复杂度。
在编程时，开始忘记include<string>了，导致对字符串的操作无法完成，程序出错，后来对 num的操作放错了位置，结果虽然对了，但添加了断点之后发现逻辑有些问题，最终都改了过来。
项目日志：
这次的程序并不复杂，主要代码只有短短二十几行，没有用掉太多时间。