AOJ 1074 Popularity Estimation
問題
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1074.
日本語。
解法
i秒後に何人映っているかをメモしておけば簡単。やるだけ。 計算量は*O(nm)ぐらいでいいのかな。
コード
int main(){ int n, m, d; char name[256]; while(scanf("%d", &n) && n){ vector< pair<int, string> >res(n); vector< vector<int> >in(n); vector<int>num(30); rep(i, n){ scanf("%s%d", name, &m); res[i] = make_pair(0, name); rep(j, m){ scanf("%d", &d); in[i].push_back(d); num[d]++; } } rep(i, n){ rep(j, in[i].size()){ res[i].first += n + 1 - num[in[i][j]]; } } sort(res.begin(), res.end()); printf("%d %s\n", res[0].first, res[0].second.c_str()); } return 0; }