soj 4389模擬

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;
}