[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:归并排序......

天涯犹在，不诉薄凉。