781. 森林中的兔子

报相同数字的兔子中（如n个兔子报的数字都是m，即[m, m, … m]）
- 如果n+1<=m (如 [6,6]) ,则可以认为这些兔子都是同一种颜色,可以抱成一团,兔子个数为 （m+1）*（n//(m+1)）
- 如果n+1>m
  - 如果正好能抱成完整的团（即 6%(2+1)==0）（如[2,2,2,2,2,2]，n=6，m=2,能抱2个团）,则兔子个数为 （2+1）*(6//(2+1))=6
  - 如果抱团后仍然后剩下的（即7%（2+1）！=0）（如[2,2,2,2,2,2,2]，n=7,m=2,需要抱3团），则兔子个数为（2+1）*（6//(2+1)+1）
  - 这两种情况可以归纳为向上取整

class Solution:
    def numRabbits(self, answers ):
        import math
        import collections
        dic=collections.defaultdict(int)
        # 统计各个元素的个数
        for i in answers:
            dic[i]+=1

        res=0
        for key,val in dic.items():
            tmp=math.ceil(val/(key+1.00))
            res+=(key+1)*tmp
        return res

或者(只是向上取整的写法不同)

class Solution:
    def numRabbits(self, answers) :
        ans_dic = {}
        for i in answers:
            if i not in ans_dic:
                ans_dic[i] = 1
            else:
                ans_dic[i] += 1
        res = 0
        for key, val in ans_dic.items():
            tmp = val // (key + 1) #抱团取整
            if val % (key+1) !=0:  #抱团后仍有剩余，则+1
                tmp += 1
            res += tmp*(key+1)
        return res

C++代码

class Solution {
public:
    static constexpr int N = 1009;
    int numRabbits(vector<int>& answers) {
        vector<int> counts(N,0);
        for(auto i : answers)
            counts[i]++;
        int ans = counts[0];
        for(int i = 1; i < N; i++) {
            int per = i + 1;
            int cnt = counts[i];
            int k = counts[i]/ (i + 1); //抱团, 地板除
            if (k * per < cnt) k++;//抱团后仍有剩余，则k+1
            ans += k * per; // 当前结果为当前抱团数*（报数数字+1）
        }
        return ans;
    }
};

或者可以把地板除int k = counts[i]/ (i + 1);和 k的更新if (k * per < cnt) k++; 合并为向上取整int k = ceil(counts[i]/ float(i + 1)); //抱团. 即：

class Solution {
public:
    static constexpr int N = 1009;
    int numRabbits(vector<int>& answers) {
        vector<int> counts(N,0);
        for(auto i : answers)
            counts[i]++;
        int ans = counts[0];
        for(int i = 1; i < N; i++) {
            int per = i + 1;
            int cnt = counts[i];
            int k = ceil(counts[i]/ float(i + 1)); //抱团
            // if (k * per < cnt) k++;//抱团后仍有剩余，则k+1
            ans += k * per; // 当前结果为当前抱团数*（报数数字+1）
        }
        return ans;
    }
};