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