A33640. 均分糖果
填空题
困难
知识点
题目描述
均分糖果
题目描述
有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参考答案
#include <bits/stdc++.h>
using namespace std;
int a[10005];
int main()
{
int n,sum=0,ans=0;
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
sum+=a[i];
}
if(sum%n!=0) {
cout<<-1;return 0;
}
sum/=n;
for(int i=1;i<=n;i++){
ans=max(ans,abs(a[i]-sum));
}
cout<<ans;
return 0;
}
上一题
下一题