【Py/Java/C++三种语言OD2023C卷真题】20天拿下华为OD笔试之【贪心】2023C-小朋友来自多少小区【欧弟算法】全网注释最详细分类最全的华为OD真题题解

文章目录

题目描述与示例
- 题目描述
- 输入
- 输出
- 示例
- - 输入
  - 输出
  - 说明
解题思路
- 错误修正
- 举例讨论
- 运用贪心
代码
- Python
- Java
- C++
- 时空复杂度
华为OD算法/大厂面试高频题算法练习冲刺训练

题目描述与示例

题目描述

幼儿园组织活动，老师布置了一个任务: 每个小朋友去了解与自己同一个小区的小朋友还有几个。我们将这些数量汇总到数组garden中，请根据这些小朋友给出的信息，计算班级小朋友至少来自几个小区？

输入

garden = [2, 2, 3]

说明:

garden数组长度最大为999。每个小区的小朋友数量最多1000人，也就是garden的范围为[0,999]

输出

一个数字

示例

输入

2 2 3

输出

说明

第一个小朋友反馈有两个小朋友和自己同一小区，即此小区有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

对于示例三，情况稍微有些变化，答案是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 dic = new HashMap();

        while (scanner.hasNext()) {
            int val = scanner.nextInt();
            dic.put(val, dic.getOrDefault(val, 0) + 1);
        }

        int ans = 0;
        for (Map.Entry 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++

#include 
#include 
#include 

using namespace std;

int main() {
    unordered_map dic;
    int val;
    while (cin >> val) {
        dic[val]++;
    }

    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(m + 1)) * (m + 1);
    }

    cout << ans << endl;

    return 0;
}

时空复杂度

时间复杂度：O(N)。一次遍历哈希表。

空间复杂度：O(N)。哈希表所占空间。

华为OD算法/大厂面试高频题算法练习冲刺训练

华为OD算法/大厂面试高频题算法冲刺训练目前开始常态化报名！目前已服务100+同学成功上岸！
课程讲师为全网50w+粉丝编程博主@吴师兄学算法以及小红书头部编程博主@闭着眼睛学数理化
每期人数维持在20人内，保证能够最大限度地满足到每一个同学的需求，达到和1v1同样的学习效果！
60+天陪伴式学习，40+直播课时，300+动画图解视频，300+LeetCode经典题，200+华为OD真题/大厂真题，还有简历修改、模拟面试、专属HR对接将为你解锁
可上全网独家的欧弟OJ系统练习华子OD、大厂真题
可查看链接大厂真题汇总 & OD真题汇总(持续更新)
绿色聊天软件戳 od1336了解更多