题解#森林中的兔子#

'''
解题思路：
如有 x 只兔子都回答 y，则至少有 ceil(x/(y+1))*(y+1) 只兔子
'''
class Solution:
    def numRabbits(self, answers: List[int]) -> int:

        if not answers:
            return 0

        A = answers
        n = len(answers)        
        print(A)

        Dic = {}
        for i in range(n):
            a = A[i]
            if a not in Dic:
                Dic[a] = 1
            else:
                Dic[a] += 1
        #print(Dic)

        res = 0
        for key in Dic:            
            x = Dic[key]            # 有 x 只兔子都回答 y
            y = key
            print('x=',Dic[key],'y=',key)

            # 如有 x 只兔子都回答 y，则至少有 ceil(x/(y+1))*(y+1) 只兔子
            if x%(y+1)==0:
                res += x
            else:
                res += (x//(y+1)+1)*(y+1)

        print(res)        
        return res            

answers = [1, 1, 2] # 5
answers = [10, 10, 10] # 11
t = Solution().numRabbits(answers)
print(t)