soj 4389模拟

学习：1.开始没有注意到题目中对于帖子数大于1/2的描述，纯暴力计数，各种超！

2.后来发现按顺序扫描每一个数看是否有它在数组中的数量大于1/2,是则找到。我的代码：

#include
  
   
#include
   
     int str[10000000]; int main(void) { int n; scanf("%d",&n); while(n--) { int m,cout=0; scanf("%d",&m); for(int i=0;i
    
     =m/2+1) { printf("%d\n",str[i]); goto l1; } } } } str[i]=-1; cout=0; } l1: cout=0; } return 0; } 
    
   
  

解题报告给出了比较先进的方法：假定第一个数是并计数count为1，以后遇见和它相同的就count自增一，当count为0时，可以就变为当前读入的数，最后剩下的可以必然是要找的大于1/2的数。给出代码：

#include
  
   
#include
   
     int str[10000000]; int main(void) { int n; scanf("%d",&n); while(n--){ int m,count=0,x,key=-1; scanf("%d",&m); while(m--){ scanf("%d",&x); if(x!=key) count--; else count++; if(count<0) { key=x; count=0; } } printf("%d\n",key); } return 0; }