読者です 読者をやめる 読者になる 読者になる

AOJ 1008 What Color Is The Universe?

404 Not Found

集合が与えられるので集合の半分より大きく占領している要素出力しろ。

なんか2^31とか書いてるんでそれぞれの配列用意したら死ぬと思ったのでmap実装。

#include <iostream>
#include <map>
using namespace std;

int main(){
	map<int,int> con;
	int t,n;
	while(cin >> n && n){
		con.clear();
		for(int i=0;i<n;i++){
			cin >> t;
			con[t]++;
		}
		map<int,int>::iterator it = con.begin();
		while(it != con.end()){
			if( (*it).second > n/2 ){cout << (*it).first << endl;break;}
			++it;
			if(it == con.end())cout << "NO COLOR" << endl;
		}
	}
}

クソ非効率的なリニアサーチ。

適当にショートコーディング後の方が全てにおいて効率的。

182Byte

#include<cstdio>
#include<map>
int main(){
	for(int t,n,r,i;scanf("%d",&n),n;printf(~r?"%d\n":"NO COLOR\n",r)){
		std::map<int,int>c;
		r=-1;
		for(i=0;i++<n;r=++c[t]>n/2?t:r)
			scanf("%d",&t);
	}
}

最近FizzBuzzチックな問題しか解いてない・・・やべぇよ・・・やべぇよ・・・。