题解

题面描述

某个幼儿园有未知个小朋友，部分小朋友看到与自己衣服颜色相同的小朋友的个数。将数据汇总到一个整数数组$colors$，其中$colors[i]$表示第$i$个小朋友看到的与自己颜色相同的小朋友的个数，不包括小朋友自己。现在给你一个数组$colors$，请计算幼儿园中小朋友最少有几个。

思路

为了计算幼儿园中小朋友的最少数量，首先统计每个孩子看到的同色小朋友数量（即数组中的每个$j$）出现的频率。然后，对于每个不同的$j$，计算至少需要多少个由$j + 1$个小朋友组成的同色组，以覆盖所有看到$j$个同色小朋友的孩子。具体来说，使用向上取整的方法将频率除以组大小，得到需要的组数。最后，将所有同色组的小朋友数量累加，得到幼儿园中小朋友的最少总数。

1. 统计每个$j$出现的频率：$j$表示一个小朋友看到的同色小朋友的数量，即一个颜色组至少有$j + 1$个小朋友。
2. 计算每个$j$对应的颜色组数量：对于每个$j$，将其出现的次数$freq_j$除以$j + 1$，向上取整，得到需要的颜色组数。
3. 计算总小朋友数：将每个$j$对应的颜色组数乘以$j + 1$，然后累加所有颜色组的小朋友数，得到幼儿园中小朋友的最少数量。

cpp

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    // 统计每个j出现的频率
    unordered_map<int, int> freq;
    string s;
    // 读取整个输入
    while(cin >> s){
        int num = stoi(s);
        freq[num]++;
    }
    
    ll total = 0;
    // 遍历每个j
    for(auto &[j, count] : freq){
        // 每组需要j+1个小朋友
        ll group_size = j + 1;
        // 需要的组数，向上取整
        ll groups = (count + group_size - 1) / group_size;
        // 总小朋友数增加
        total += groups * group_size;
    }
    
    cout << total;
}

python

import math
from collections import defaultdict
import sys

def main():
    freq = defaultdict(int)
    # 读取所有输入
    for s in sys.stdin.read().split():
        j = int(s)
        freq[j] += 1
    
    total = 0
    for j, count in freq.items():
        group_size = j + 1
        groups = math.ceil(count / group_size)
        total += groups * group_size
    print(total)

if __name__ == "__main__":
    main()

java

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] tokens = br.readLine().split("\\s+");
        // 统计每个j的频率
        HashMap<Integer, Integer> freq = new HashMap<>();
        for(String token : tokens){
            int j = Integer.parseInt(token);
            freq.put(j, freq.getOrDefault(j, 0) + 1);
        }
        
        long total = 0;
        for(Map.Entry<Integer, Integer> entry : freq.entrySet()){
            int j = entry.getKey();
            int count = entry.getValue();
            int groupSize = j + 1;
            // 计算需要的组数，向上取整
            long groups = (count + groupSize - 1) / groupSize;
            total += groups * groupSize;
        }
        System.out.println(total);
    }
}

题目内容

某个幼儿园有未知个小朋友，部分小朋友我出跟自己衣服一样颜色的小朋友个数,将数据汇总到一个整数数组$colors$，其中$colors[i]$是第$i$个小朋友看到的个数，不包括小朋友自己。现在给你一个数组$colors$，请计算幼儿园中小朋友最少有几个。

输入描述

以空格隔开的数组$colors，colors[i] = j, 1<=i<=1000000; 1<=j<=100000$

输出描述

一个整数，小朋友最少有几个

样例1

输入

1 1 2

输出

5

说明

$1$、第一个小朋友看到同色$1$个人，第二个小朋友看到同色$1$个人，第三个小朋友看到同色$2$个。幼儿园至少有$5$个小朋友。

$2$、算法步骤: 第一个小朋友和第二个小朋友他他们看到的同色都是$1$个，最少是他们互相看见，这样就有$2$个小朋友;第三个小朋友看到同色$2$个，最少$3$是$3$个小朋友;$2$个加上$3$个就是$5$个