1008-What Color is The Universe?
http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=1008
最初はstd::countで解こうと思ったけど速度が足りなかった。
goto文をC++で初めて使った。
問題概要
数列{an}が与えられ、それの最頻値の個数が数列の項数の過半数かどうかを調べる問題。
最頻値の個数が過半数を超える場合は最頻値を出力。
超えない場合は"NO COLOR"と出力する。
考え方
与えられた数列をソートし、条件をみたすような値が存在するかを調べる。
計算量はO(n log n)
実装(C++)
#include<cstdio> #include<algorithm> #include<cstring> int n,i; int main(){ for (;;i=0){ scanf("%d",&n); if(n==0) break; int a[n]; for(i=0;i<n;i++){scanf("%d",&a[i]);} std::sort(a,a+n); int b[n];memset(b,0,n*4); int t=0; b[0]=1; for(i=1;i<n;i++)if(a[i-1]==a[i]){b[t]++;}else{if(b[t]>n/2){printf("%d\n",a[i-1]);goto a;}t++;b[t]=1;} if(b[t]>n/2){printf("%d\n",a[i-1]);goto a;} puts("NO COLOR"); a:; } return 0; }