UVa-11286, POJ-3640 : Conformity
問題概要
N(<1000)人の生徒は100~499の数字を5つ選ぶ。最も多く選ばれた集合(タイの場合は全部)を選んだ生徒の数を答える問題。
解法
数字5個の集合はソートしてから500進数だと思えば64ビットに収まる。なのでmap
acceptされたコード
計算量O(N * log N)。
#include <cstdio> #include <algorithm> #include <map> using namespace std; typedef long long int64; int N; int solve(){ map<int64, int> dict; int maxi = 0; for(int i=0; i<N; i++){ int xs[5]; scanf("%d%d%d%d%d",xs, xs+1, xs+2, xs+3, xs+4); sort(xs, xs+5); int64 hash = 0; for(int j=0; j<5; j++){ hash = hash * 500 + xs[j]; } maxi = max(maxi, ++dict[hash]); } int ans = 0; for(map<int64, int>::iterator itr = dict.begin(); itr!=dict.end(); itr++){ if(itr->second == maxi){ ans += maxi; } } return ans; } int main(){ while(scanf("%d", &N), N){ printf("%d\n", solve()); } return 0; }