[2021.4.20打卡]LeetCode781. 森林中的兔子

LeetCode781. 森林中的兔子

示例:
输入: answers = [1, 1, 2]
输出: 5
解释:
两只回答了 "1" 的兔子可能有相同的颜色，设为红色。
之后回答了 "2" 的兔子不会是红色，否则他们的回答会相互矛盾。
设回答了 "2" 的兔子为蓝色。
此外，森林中还应有另外 2 只蓝色兔子的回答没有包含在数组中。
因此森林中兔子的最少数量是 5: 3 只回答的和 2 只没有回答的。

输入: answers = [10, 10, 10]
输出: 11

输入: answers = []
输出: 0
说明:

answers 的长度最大为1000。
answers[i] 是在 [0, 999] 范围内的整数。

链接：https://leetcode-cn.com/problems/rabbits-in-forest

代码如下:

 1 class Solution {
 2 public:
 3     int numRabbits(vector<int>& answers) {
 4         unordered_map<int,int> cnt;
 5         int sum=0;
 6         for(auto m: answers)cnt[m]++;
 7         for(auto [x,y]: cnt)
 8             sum += (x+y)/(x+1)*(x+1);//★上取整
 9         return sum;
10     }
11 };

①用hash来统计answers中每个数字出现的次数；

②开始处理哈希表里面的统计结果了； 例如， 5出现了8次， 那么至少得2*（5+1）只兔子； 如果5出现了6次呢？ 至少需要6只兔子； 如果5出现了3次呢？ 还是6只兔子； 当val出现了t次， 如果t%（val+1） == 0， 需要（t/（val+1））*（val+1）只兔子； 如果没有整除， 则至少需要(t/(val+1)+1)*(val+1)只兔子,综上归纳为(val+t)/(val+1)*(val+1),即先上取整再乘组内人数

----明天份小flag:归并排序......

[2021.4.20打卡]LeetCode781. 森林中的兔子

原文：https://www.cnblogs.com/Knight02/p/14683500.html