题目描述与示例
题目描述
幼儿园组织活动，老师布置了一个任务: 每个小朋友去了解与自己同一个小区的小朋友还有几个。我们将这些数量汇总到数组garden中，请根据这些小朋友给出的信息，计算班级小朋友至少来自几个小区？
输入
garden = [2, 2, 3]
说明:
garden`数组长度最大为`999`。每个小区的小朋友数量最多`1000`人，也就是`garden`的范围为`[0,999]
输出
一个数字
示例
输入
2 2 3
输出
7
说明
第一个小朋友反馈有两个小朋友和自己同一小区，即此小区有3个小朋友
第二个小朋友反馈有两个小朋友和自己同一小区，即此小区有3个小朋友。
这两个小朋友，可能是同一小区的，且此小区的小朋友只有3个人。
第三个小朋友反馈还有3个小朋友与自己同一小区，则这些小朋友只能是另外一个小区的。这个小区有4个小朋友。
班级里至少有3+4 = 7个小朋友。
解题思路
错误修正
首先题目描述中的设问是有问题的。
按照示例和说明，“计算班级小朋友至少来自几个小区?”这个问题是不正确。正确的问题应该是“计算班级里至少有几个小朋友？”。
另外，从示例可以得知，虽然最终算出班级里至少有7个小朋友，但只有3个小朋友给出了小区信息。所以garden数组的长度，并不能直接得到小朋友的总数。
举例讨论
排除掉上述题干干扰，这个问题是一个非常有意思的题目。
示例其实提供了一个思考方向。思考以下三组不同的示例。
示例一
2 2 3
示例一和题目给定的示例是一样的。答案是7。
示例二
2 2 2 3
对于示例二，答案也是7。
因为对于第三个反馈有2个小朋友和自己来自同一小区的小朋友来说，他有可能和前两个小朋友也位于同一个小区。
也就是说，这个人数为3的小区，每个小朋友都反馈了人数信息。
最后一个小朋友反馈还有3个小朋友与自己同一小区，则这些小朋友只能是另外一个小区的。这个小区有4个小朋友。
故班级里至少有3+4 = 7个小朋友。
示例三
2 2 2 2 3
ceil(4 / (2+1)) * （2+1） = 2 * 3 = 6
ceil(1 / (3+1)) * （3+1） = 1 * 4 = 4
对于示例三，情况稍微有些变化，答案是10。
和示例二类似，前三个小朋友可以来自同一个人数为3的小区，最后一个小朋友来自一个人数为4的小区。
对于第四个小朋友，他也反馈有2个小朋友和自己来自同一小区，但他不可能和前三个小朋友是同一个小区了，因为这个小区最多只能有3个人是同一个小区的。
所以第四个小朋友必须单独来自一个人数为3的小区。
故班级里至少有3+3+4 = 10个小朋友。
运用贪心
例子举到这里应该能够看出端倪了。
首先，如果两个小朋友所反馈的人数不一致，那么他们必然不可能来自同一个小区。这是非常显而易见的结论。
因此我们只需要考虑反馈人数相同的那些小朋友的数量即可。
假设存在n个小朋友均反馈有m个其他小朋友和他来自同一小区，那么小区人数应该为m+1（+1表示包含这个小朋友自己）。
为了使得总的小区数尽可能地少，我们会贪心地将尽可能多的小朋友安排到同一个小区里。一个小区的人数上限为m+1，因此此时所需要的小区数量为ceil(n ``/ (m+1)``)。
这些小区所包含的小朋友数量为ceil(n ``/ (m+1)``) * (m+1)。
对于garden里的所有信息，构建哈希表计数器dic，dic[m] = n表示反馈人数为m的小朋友的数量为n。
再遍历哈希表即可解决问题。其代码如下
dic = Counter(garden)
ans = 0
for m, n in dic.items():
ans += ceil(n / (m+1)) * (m+1)
代码
Python
# 题目：【贪心】2023C-小朋友来自多少小区
# 分值：100
# 作者：闭着眼睛学数理化
# 算法：贪心，哈希表
# 代码看不懂的地方，请直接在群上提问
from collections import Counter
from math import ceil
garden = list(map(int, input().split()))
# 构建哈希表计数器
# dic[m] = n表示反馈人数为m的小朋友的数量为n
dic = Counter(garden)
ans = 0
# 遍历哈希表，运用贪心算法
for m, n in dic.items():
ans += ceil(n / (m+1)) * (m+1)
print(ans)
Java
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
Map<Integer, Integer> dic = new HashMap<>();
while (scanner.hasNext()) {
int val = scanner.nextInt();
dic.put(val, dic.getOrDefault(val, 0) + 1);
}
int ans = 0;
for (Map.Entry<Integer, Integer> entry : dic.entrySet()) {
int m = entry.getKey();
int n = entry.getValue();
ans += Math.ceil((double) n / (m + 1)) * (m + 1);
}
System.out.println(ans);
}
}
C++
“`C++
#include <iostream>
#include <unordered_map>
#include <cmath>
using namespace std;
int main() {
unordered_map<int, int> dic;
int val;
while (cin >> val) {
dic[val]++;
}
<pre><code>int ans = 0;
for (auto it = dic.begin(); it != dic.end(); ++it) {
int m = it->first;
int n = it->second;
ans += ceil(n / static_cast<double>(m + 1)) * (m + 1);
}
cout << ans << endl;
return 0;
</code></pre>
}
“`
时空复杂度
时间复杂度：O(N)。一次遍历哈希表。
空间复杂度：O(N)。哈希表所占空间。
说明
华为OD机试有三道题⽬，第⼀道和第⼆道属于简单或中等题，分值为 100 分，第三道为中等或困难题，分值为 200分，总分为 400 分。
机试分数越⾼评级越⾼，⼯资也就越⾼。
关于华为 OD 机试更加详细的介绍可以查看这篇⽂章：华为OD机考须知
关于机考题目汇总可以看这篇文章：华为OD机试真题 2023 A+B+C+D卷 + 2024新卷（Python&Java&C++）⽬录汇总（每⽇更新）
