【贪心】2023C-小朋友来自多少小区

题目描述与示例

本题练习地址：https://www.algomooc.com/problem/P3106

题目描述

幼儿园组织活动，老师布置了一个任务: 每个小朋友去了解与自己同一个小区的小朋友还有几个。我们将这些数量汇总到数组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
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++

#include <iostream>
#include <unordered_map>
#include <cmath>

using namespace std;

int main() {
    unordered_map<int, int> 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<double>(m + 1)) * (m + 1);
    }

    cout << ans << endl;

    return 0;
}

时空复杂度

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

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