SRM499 Div1 Easy(250), Div2 Medium(500) ColorfulRabbits

TopCoder

ColorfulRabbits

同じ色のウサギが異なる匹数を答えることはない。xと答えたウサギがy匹いた場合、ある色のウサギはx+1匹。y>x+1ならば他の色のウサギがいるはず……と考えると、少なくとも⌈y/(x+1)⌉*(x+1)匹のウサギがいる。

#include <vector>
#include <set>
#include <algorithm>
using namespace std;

class ColorfulRabbits{public:
int getMinimum( vector <int> replies )
{
    set<int> s(replies.begin(),replies.end());

    int ans = 0;
    for ( set<int>::iterator it=s.begin(); it!=s.end(); it++ )
    {
        int c = count(replies.begin(),replies.end(),*it);
        int t = *it+1;
        ans += (c-1)/t*t+t;
    }
    return (int)ans;
}};