小朋友来自多少小区 - 华为OD统一考试(C卷)

OD统一考试（C卷）

分值： 100分

题解： Java / Python / C++

alt

题目描述

幼儿园组织活动，老师布置了一个任务：

每个小朋友去了解与自己同一个小区的小朋友还有几个。

我们将这些数量汇总到数组 garden 中。

请根据这些小朋友给出的信息，计算班级小朋友至少来自几个小区？

输入描述

输入：garden[] = {2, 2, 3}

说明：

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

输出描述

输出：7

示例1

输入：
2 2 3

输出：
7

说明：
第一个小朋友反馈有两个小朋友和自己同一小区，即此小区有3个小朋友。
第二个小朋友反馈有两个小朋友和自己同一小区，即此小区有3个小朋友。
这两个小朋友，可能是同一小区的，且此小区的小朋友只有3个人。
第三个小区反馈还有3个小朋友与自己同一小区，则这些小朋友只能是另外一个小区的。这个小区有4个小朋友。

题解

本题出的有误，输出其实是至少的小朋友数量，而不是班级小朋友至少来自几个小区。

通过例子来说明：

garden = {2,2} // 可能来自同一个小区，学生人数 = 1(自己) + 2(其他小朋友个数)

graden = {2,2,2} // 可能来自同一个小区，学生人数 = 1(自己) + 2(其他小朋友个数)

graden = {2,2,2,2} // 不可能来自同一个小区，至少来自 2 个小区，学生人数 = 2 * （1 + 2）

假如有 v 个小朋友说来自其他小区小朋友有 k 个：

则至少有小区个数： v / (k + 1) 向上取整 == (v + k) / (k + 1)
则每个小区的人数： 1(自己) + k(其他小朋友人数)
则至少小朋友数： (v + k) / (k + 1) * ( k + 1)

根据以上的总结，就可以对小朋友给出的数据进行统计，统计完后再根据统计数据计算出总的学生人数。

Java

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;
/**
 * @author code5bug
 */
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        Map<Integer, Integer> cnt = new HashMap<>();

        // 读取输入并统计数字出现次数
        while (scanner.hasNextInt()) {
            int t = scanner.nextInt();
            cnt.put(t, cnt.getOrDefault(t, 0) + 1);
        }

        int tot = 0;
        // 遍历统计结果
        for (Map.Entry<Integer, Integer> entry : cnt.entrySet()) {
            int k = entry.getKey();
            int v = entry.getValue();

            // 计算小区个数，向上取整
            int group = (v + k) / (k + 1);
            // 计算总人数
            tot += group * (k + 1);
        }

        System.out.println(tot);
    }
}

Python

from collections import defaultdict

def main():
    cnt = defaultdict(int)  # 使用 defaultdict 初始化计数字典
    tot = 0

    # 统计每个数出现的次数
    for t in list(map(int, input().split())):
        cnt[t] += 1

    # 遍历计数字典，计算总人数
    for k, v in cnt.items():
        group = (v + k) // (k + 1)  # 小区个数，向上取整
        tot += group * (k + 1)       # 每个小区人数（k + 1）

    print(tot)


if __name__ == "__main__":
    main()

C++

以下是将 Java 代码翻译成 Python 的版本，并在关键代码上添加注释：
#include <bits/stdc++.h>
using namespace std;

int main()
{
    unordered_map<int, int> cnt;
    int                     t;
    while (cin >> t) {
        cnt[t]++;
    }

    int tot;
    for (const auto& it : cnt) {
        int k = it.first, v = it.second;

        int group = (v + k) / (k + 1);   // 小区个数，向上取整
        tot += group * (k + 1);          // 每个小区人数（k + 1）
    }

    cout << tot << endl;

    return 0;
}