找水王问题

1.题目：

三人行设计了一个灌水论坛。信息学院的学生都喜欢在上面交流灌水，传说在论坛上有一个“水王”，他不但喜欢发帖，还会回复其他ID发的每个帖子。坊间风闻该“水王”发帖数目超过了帖子数目的一半。

如果你有一张当前论坛的帖子（包括回帖）列表，其中帖子的作者的ID也在其中，你能快速的找到这个传说中的水王吗？

2.设计思路：

采用消消乐的逆向思想，把相邻的两个不同id依次消掉，由于水王id多于总数的一半，所以最终剩下的一定是水王id。

3.源代码：

 1 #include <iostream.h>
 2 #include <stdlib.h>
 3 int Id=0; 
 4 int count=0; 
 5 void FindId(int arr[],int n) 
 6 { 
 7     for (int i=0;i<n;i++)   
 8     {   
 9         if (count==0)  
10         {   
11             count++;
12             Id=arr[i];
13         }   
14         else  
15         {   
16             if(Id==arr[i]) 
17                 count++;   
18             else         
19                 count--;  
20         }   
21     }   
22 }   
23 int main() 
24 { 
25     int n;  
26     int *arr=new int[]; 
27     cout<<"请输入总的帖子数:"; 
28     cin>>n; 
29     cout<<"请输入每个水军的ID:"<<endl; 
30     for(int i=0;i<n;i++) 
31     { 
32         cin>>arr[i]; 
33     } 
34     FindId(arr,n); 
35     cout<<"水王的ID是:"<<Id<<endl;; 
36     return 0;
37 }

4.结果截图：

5.心得体会：

本次编程实践也是重在设计思想，拿到题目还是老想法，先从最笨的方法入手，继而对可实现的方法进行优化，最终达到时间复杂度的要求，这点对于以后的编程开发有很大的帮助。