# 781.森林中的兔子

## 问题描述
[781. 森林中的兔子 (Medium)](https://leetcode.cn/problems/rabbits-in-forest/)

森林中有未知数量的兔子。提问其中若干只兔子 **"还有多少只兔子与你（指被提问的兔子）颜色相同?"**
，将答案收集到一个整数数组 `answers` 中，其中 `answers[i]` 是第 `i` 只兔子的回答。
给你数组 `answers` ，返回森林中兔子的最少数量。
**示例 1：**
```
输入：answers = [1,1,2]
输出：5
解释：
两只回答了 "1" 的兔子可能有相同的颜色，设为红色。
之后回答了 "2" 的兔子不会是红色，否则他们的回答会相互矛盾。
设回答了 "2" 的兔子为蓝色。
此外，森林中还应有另外 2 只蓝色兔子的回答没有包含在数组中。
因此森林中兔子的最少数量是 5 只：3 只回答的和 2 只没有回答的。
```
**示例 2：**
```
输入：answers = [10,10,10]
输出：11
```
**提示：**
- `1 <= answers.length <= 1000`
- `0 <= answers[i] < 1000`

## 解题思路
从题目中给出的例子我们可以发现，要想让兔子数量最小，那么要尽量让回答结果相同的兔子是同一个颜色的；

我们用一个哈希表`unordered_map<int, int> ump`来记录每种结果有多少只兔子回答了，`key`为回答结果，`value`是回答该结果的兔子的数量；

如果`ump[i] > i + 1`，说明这批兔子至少有不止一种颜色，颜色数为`(ump[i] - 1) / (i + 1) + 1`，每种颜色有`i + 1`个兔子。

## 代码
```cpp
class Solution {
  public:
    int numRabbits(vector<int> &answers) {
        unordered_map<int, int> ump;
        int res = 0;
        for (auto &num : answers) {
            ump[num]++;
        }
        for (auto &num : ump) {
            // if (num.second % (num.first + 1) == 0) {
            //     res += num.second;
            // } else {
            //     res  += (num.second / (num.first + 1) + 1) * (num.first + 1);
            // }
            res += ((num.second - 1) / (num.first + 1) + 1) * (num.first + 1);
        }
        return res;
    }
};
```