首页 > 试题广场 >

糖果谜题

[编程题]糖果谜题
  • 热度指数:6541 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解
小明是幼儿园的一名老师。某天幼儿园园长给小朋友们每人发一颗糖果,小朋友们拿到后发现有一些同学拿到的糖果颜色和自己相同,有一些同学糖果颜色和自己不同。
假定每个小朋友只知道有多少同学和自己拿到了相同颜色的糖果。
上课后,有一部分小朋友兴奋的把这一结果告诉小明老师,并让小明老师猜一猜,最少有多少同学拿到了糖果。
例如有三个小朋友告诉小明老师这一结果如下:
其中第一个小朋友发现有1人和自己糖果颜色一样,第二个小朋友也发现有1人和自己糖果颜色一样,第三个小朋友发现有3人和自己糖果颜色一样。
第一二个小朋友可互相认为对方和自己颜色相同,比如红色;
第三个小朋友不可能再为红色(否则第一二个小朋友会发现有2人和自己糖果颜色相同),假设他拿到的为蓝色糖果,那么至少还有另外3位同学拿到蓝色的糖果,最终至少有6位小朋友拿到了糖果。
现在请你帮助小明老师解答下这个谜题。

输入描述:
假定部分小朋友的回答用空格间隔,如 1 1 3


输出描述:
直接打印最少有多少位小朋友拿到糖果
如 6
示例1

输入

1 1 3

输出

6
示例2

输入

0 0 0

输出

3

说明

三位小朋友都没发现有人和自己的颜色相同,所以最少的情况就是三位小朋友糖果的颜色均不同

备注:
其中回答学生个数最多1000
每个学生回答的答案在[0,999]之间
头像 牛客题解官
发表于 2020-06-05 16:14:10
题解: 题目难度:中等 知识点:数学逻辑、动态数组、map 首先要明确:当小朋友所报数字相同时,小朋友可互相认为对方和自己颜色相同;当小朋友所报数字不相同时,那么双方颜色一定不相同。 方法一: 步骤一:首先将小朋友所报数字放入动态数组v中,记录小朋友人数res初始化值为0。 步骤二:构造map依次对 展开全文
头像 生命不息手撕不止
发表于 2019-08-10 11:20:32
思想就是用map记录每个相同数字num的次数count;1、count<=num+1,则该num对应的人数为num+1;2、count>num,则进行num+1,count -= num;之后再进行判断,因为每一个num对应的人数最多为num+1,所以要减去num重新判断。即比如2 2 展开全文