刷题刷出新高度,偷偷领先!偷偷领先!偷偷领先! 关注我们,悄悄成为最优秀的自己!

简答题

均分糖果

题目描述:

有n 个小朋友站成一排,起初,从左到右每个小朋友分别有a1、a2、a3、...、an 颗糖果。

接下来每一轮老师都会选择一个或多个有糖果的小朋友,他们会将自己的一颗糖果,送给一个与他相邻的小朋友(左边或者右边的小朋友)。

请计算最少需要经过多少轮,才能使所有小朋友的糖果数量都相等?如果做不到,则输出-1。

例1:

n = 3,表示有三个小朋友,他们起初的糖果数量分别为1、0、5;

以下是一种最少轮次的情况:

第一轮,选择第三个小朋友,将1 颗糖送给第二个小朋友,之后三个小朋友的糖果数量依次为1、1、4:

1 0 <-- 5 => 1 1 4

第二轮,选择第二个和第三个小朋友,第二个小朋友将1 颗糖送给第一个小朋友,第三个小朋友将1 颗糖给第二个小朋友,之后三个小朋友的糖果数量依次为2、1、3:

1 <-- 1 <-- 4 => 2 1 3

第三轮,选择第三个小朋友,将1 颗糖送给第二个小朋友,之后三个小朋友的糖果数量依次为2、2、2:

2 1 <-- 3 => 2 2 2

最少需要经过3 轮,才能使三个小朋友的糖果数量都相等。

例2:

n = 3,表示有三个小朋友,他们起初的糖果数量分别为0、2、0;

无论如何操作,都不可能使三个小朋友的糖果数量都相等,故输出-1。

输入描述:

第一行输入一个整数n(1≤n≤10^4),表示小朋友的人数

第二行输入n 个整数a1,a2,a3、...、an(0≤ai≤10^5),分别表示从左到右每个小朋友起初拥有的糖果数量,整数之间以一个空格隔开

输出描述:

输出一个整数,表示至少需要经过多少轮,才能使所有小朋友的糖果数量都相等;如果做不到,则输出-1


样例输入:

3
1 0 5

样例输出:

3

使用微信搜索喵呜刷题,轻松应对考试!

答案:

对于每个小朋友,我们计算他的糖果数量与平均糖果数量的差值。如果差值大于0,说明这个小朋友的糖果数量比平均值多,他会送出糖果;如果差值小于0,说明这个小朋友的糖果数量比平均值少,他会收到糖果。首先,我们计算所有小朋友的糖果总数和平均值。如果总数不能被n整除,那么无论如何操作,都无法使所有小朋友的糖果数量都相等,直接输出-1。否则,我们遍历每个小朋友,计算他的糖果数量与平均值的差值。对于差值大于0的小朋友,我们将其差值累加到发送糖果的次数中;对于差值小于0的小朋友,我们同样将其差值的绝对值累加到接收糖果的次数中。最后,我们返回发送糖果的次数和接收糖果的次数中的较大值,即为最少需要经过的轮数。

解析:

【喵呜刷题小喵解析】:
这个题目是一个经典的数学问题,可以通过模拟和计算来解决。首先,我们需要理解题目的要求,即需要计算最少需要经过多少轮,才能使所有小朋友的糖果数量都相等。

对于每个小朋友,他的糖果数量与平均值的差值决定了他是发送糖果还是接收糖果。如果差值大于0,说明这个小朋友的糖果数量比平均值多,他会送出糖果;如果差值小于0,说明这个小朋友的糖果数量比平均值少,他会收到糖果。

我们可以通过遍历每个小朋友,计算他的差值,并累加发送糖果的次数和接收糖果的次数,从而得到最少需要经过的轮数。需要注意的是,如果总糖果数不能被n整除,那么无论如何操作,都无法使所有小朋友的糖果数量都相等,直接输出-1。

这种方法的时间复杂度是O(n),其中n是小朋友的数量。因此,对于较大的n,我们需要在计算差值和累加次数时,注意优化算法,避免超时。
创作类型:
原创

本文链接:均分糖果 题目描述: 有n 个小朋友站成一排,起初,从左到右每个小朋友分别有a1、a2、a3、...

版权声明:本站点所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明文章出处。

让学习像火箭一样快速,微信扫码,获取考试解析、体验刷题服务,开启你的学习加速器!

分享考题
share