华为OD统一考试 - 小朋友至少有几个

题目描述

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

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

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

请根据这些小朋友给出的信息，计算小朋友至少有几个？

输入描述

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

输出描述

输出：7

备注

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

用例

题目解析

本题的输出其实是至少的小朋友数量

假设：

• 小朋友A反馈有x个人与自己的小区相同
• 小朋友B反馈有y个人与自己的小区相同

那么，在什么情况下，可以假设小朋友A和小朋友B是同一个小区的？

答案：只有当x == y时，A和B的小区才可能是相同的。

比如：

小朋友A反馈有1个人和自己小区相同，小朋友B反馈有2个人和自己小区相同。

那么此时小朋友A和小朋友B的小区必然不同。

比如：

小朋友A反馈有1个人和自己小区相同，小朋友B也反馈有1个人和自己小区相同。

那么此时小朋友A，B可能是同一个小区的。并且可以进一步假设该小区只有A，B两个小朋友，即我们可以认为A，B发生了合并。

假设：有x个小朋友都反馈有y个人与自己小区相同

那么此时“至多”有 x * (y+1) 个小朋友，即这x个小朋友的小区各不相同，而这x个小朋友的每一个人都反馈还有y个人的小区和自己相同，即每一个小区都有 y + 1 人。

那么“至少”情况该