返回目录

题目描述

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

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

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

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

输入描述

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

输出描述

输出：7

备注

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

示例：

解题思路

题目要求计算的是班级小朋友至少来自几个小区，但实际上根据上面的用例看：本题的输出其实是至少的小朋友数量

如果两个小朋友反馈的同小区人数相同，我们可以假设他们来自同一个小区，并且将他们的小区视为一个整体进行计算。这样，我们可以通过合并相同反馈的小朋友来减少总的小区数，从而得出至少有多少小朋友的估计。

具体来说，如果有多个小朋友反馈了相同的同小区人数，我们可以将他们分成若干组，每组包含 y+1 个小朋友（因为每个小朋友包括他自己在内的小区总人数是 y+1）。

如果小朋友的数量不是 y+1 的整数倍，那么最后一组将包含不足 y+1 的小朋友，但仍然被视为一个独立的小区。因此，我们可以通过向上取整 x / (y+1) 来计算至少的小区数，其中 x 是反馈相同人数 y 的小朋友数量。

这种方法的关键在于，我们尽可能地将反馈相同的小朋友合并为同一个小区，以最小化小区的数量。通过这种策略，我们可以得出一个保守估计，即至少有多少小朋友参与了活动。

1. 为了解释这个过程，我们可以使用一个更复杂的用例：
   假设我们有以下的报告情况：

   • 有8个小朋友报告说有2个其他孩子和他们同一个小区
   • 有5个小朋友报告说有4个其他孩子和他们同一个小区
   • 有2个小朋友报告说有6个其他孩子和他们同一个小区

   我们的目标是计算至少有多少个小区。
   对于第一种情况 ：

   • 每个报告实际上代表 y + 1 = 3 个孩子。
   • 有8个报告，所以我们有 8 * 3 = 24 个孩子。
   • 这24个孩子至少来自 ceil(8 / 3) = 3 个小区，因为每3个孩子至少来自1个小区。

   对于第二种情况 ：

   • 每个报告实际上代表 y + 1 = 5 个孩子。
   • 有5个报告，所以我们有 5 * 5 = 25 个孩子。
   • 这25个孩子至少来自 ceil(5 / 5) = 1 个小区，因为每5个孩子至少来自1个小区。

   对于第三种情况 ：

   • 每个报告实际上代表 y + 1 = 7 个孩子。
   • 有2个报告，所以我们有 2 * 7 = 14 个孩子。
   • 这14个孩子至少来自 ceil(2 / 7) = 1 个小区，因为每7个孩子至少来自1个小区。

   将三种情况相加，我们得到至少有 3 + 1 + 1 = 5 个小区。

Python算法源码

import math

# 读取一行输入并按空格分割
line = input()
children_counts = list(map(int, line.split()))

# 创建一个列表用于存储每个小区的孩子数量
counts = [0] * (max(children_counts) + 1)

# 初始化结果变量为0，用于存储最终的小区数量
result = 0

# 遍历输入的孩子数量
for children in children_counts:
    # 在对应的索引位置增加孩子数量
    counts[children] += 1

# 遍历counts列表
for i in range(len(counts)):
    # 如果当前索引位置的值大于0
    if counts[i] > 0:
        # 计算每个小区的实际大小（孩子数量加上自己）
        district_size = i + 1
        # 使用ceil进行向上取整计算至少需要的小区数量，并累加到结果变量中
        result += math.ceil(counts[i] / district_size) * district_size

# 输出最终计算的小区数量
print(result)

C算法源码

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

#define MAX_SIZE 1000

int main() {
    // 读取一行输入并按空格分割
    char line[MAX_SIZE];
    fgets(line, MAX_SIZE, stdin);

    // 创建一个数组用于存储每个小区的孩子数量
    int counts[MAX_SIZE] = {0};

    // 使用 strtok 函数分割字符串
    char *token = strtok(line, " ");
    while (token != NULL) {
        // 将字符串转换为整数表示孩子数量
        int children = atoi(token);

        // 确保 counts 数组的长度足够
        while (children >= MAX_SIZE) {
            // 如果不够，则在 counts 数组末尾添加 0
            counts[MAX_SIZE - 1] = 0;
        }
        // 在对应的索引位置增加孩子数量
        counts[children]++;

        // 继续处理下一个 token
        token = strtok(NULL, " ");
    }

    // 初始化结果变量为 0，用于存储最终的小区数量
    int result = 0;

    // 遍历 counts 数组
    for (int i = 0; i < MAX_SIZE; i++) {
        // 如果当前索引位置的值大于 0
        if (counts[i] > 0) {
            // 计算每个小区的实际大小（孩子数量加上自己）
            int districtSize = i + 1;
            // 使用 ceil 进行向上取整计算至少需要的小区数量，并累加到结果变量中
            result += (int) ceil((double) counts[i] / districtSize) * districtSize;
        }
    }

    // 输出最终计算的小区数量
    printf("%d\n", result);

    return 0;
}

Java算法源码

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        // 创建一个 Scanner 对象用于读取输入
        Scanner scanner = new Scanner(System.in);

        // 读取一行输入并按空格分割
        String line = scanner.nextLine();
        String[] tokens = line.split(" ");

        // 创建一个数组用于存储每个小区的孩子数量
        int[] counts = new int[1000];

        // 遍历输入的孩子数量
        for (String token : tokens) {
            // 将字符串转换为整数表示孩子数量
            int children = Integer.parseInt(token);

            // 确保 counts 数组的长度足够
            while (children >= counts.length) {
                // 如果不够，则在 counts 数组末尾添加 0
                counts[counts.length - 1] = 0;
            }
            // 在对应的索引位置增加孩子数量
            counts[children]++;
        }

        // 初始化结果变量为 0，用于存储最终的小区数量
        int result = 0;

        // 遍历 counts 数组
        for (int i = 0; i < counts.length; i++) {
            // 如果当前索引位置的值大于 0
            if (counts[i] > 0) {
                // 计算每个小区的实际大小（孩子数量加上自己）
                int districtSize = i + 1;
                // 使用 Math.ceil 进行向上取整计算至少需要的小区数量，并累加到结果变量中
                result += (int) Math.ceil((double) counts[i] / districtSize) * districtSize;
            }
        }

        // 输出最终计算的小区数量
        System.out.println(result);
      
        // 关闭 Scanner 对象
        scanner.close();
    }
}