回答的数字相同归为一类,每一类相互独立
每一类有v只兔子回答了k
每一类的兔子有k+1个 即看最少能分成多少组
v/(k+1)的上取整
比如回答了5,说明这一类中一共有6只兔子,那么有几只兔子回答了5就很关键
比如有8只(>6)回答了5,说明至少有2类,一类中最多就6只
数学知识:a/b的上去整==(a+b-1)/b的下取整,/代表的是下取整
class Solution {
public:
int numRabbits(vector<int>& answers) {
unordered_map<int,int> cnt;
for(auto c:answers) cnt[c]++;
int res=0;
for(auto [k,v]:cnt){
res+=(v+k)/(k+1)*(k+1);
}
return res;
}
};