#538. LQ均分糖果
LQ均分糖果
均分糖果
题目描述
有 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≤104),表示小朋友的人数第二行输入 n 个整数 a1,a2,a3、...、an(0≤ai≤105),分别表示从左到右每个小朋友起初拥有的糖果数量,整数之间以一个空格隔开
输出描述
输出一个整数,表示至少需要经过多少轮,才能使所有小朋友的糖果数量都相等;如果做不到,则输出 -1
输入样例1
3
1 0 5
样例输出1
3