ColorfulRabbits srm 499 div2 mid

program topcoder

問題

http://www.topcoder.com/stat?c=problem_statement&pm=11327

方針

  • 同じ色の兎は同じ答えを返す。
  • ある兎の答えが n の時、その色の兎は丁度 n + 1 匹町の中にいる。

という条件に気を付けて数える。

答案

#include <sstream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <iostream>
#include <utility>
#include <set>
#include <cctype>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <iterator>


using namespace std;


class ColorfulRabbits{
public:
  int getMinimum(vector <int> replies){
    map<int, int> m;
    for(int i = 0; i < (int)replies.size(); i++){
      if(m.find(replies[i]) == m.end()){
	m[replies[i]] = 0;
      }
      m[replies[i]] += 1;
    }


    int ret = 0;
    for(map<int, int>::iterator it = m.begin(); it != m.end(); ++it){
      ret += (it->second / (it->first + 1)) * (it->first + 1);
      ret += it->second % (it->first + 1) ? it->first + 1 : 0;
    }
    return ret;
  }



};