SRM 548 Div2 Easy KingdomAndDucks

問題

王様はアヒルがたくさん入ったコンテナをもらった.各アヒルはそれぞれtypeがあり,コンテナに含まれる各typeのアヒルは同じ数だけある.いま幾つかサンプリングして,元のコンテナにいくつのアヒルがいたのかを推定する.複数通りある場合は最小の数を返す.

解答

サンプリングされたアヒルの種類数*typeが一致する最大のアヒルの数が答え.

class KingdomAndDucks
{
public:
  int minDucks(vector <int> duckTypes)
    {
      int n = duckTypes.size();
      vector<int> types(51, 0);
      int num_types = 0;
      int max_num = 0;
      for(int i = 0; i < n; i++){
        if (types[duckTypes[i]] == 0) num_types++;
        types[duckTypes[i]]++;
        max_num = max(max_num, types[duckTypes[i]]);
      }
      return num_types * max_num;
    }
};