×

计蒜客

  1. 题库
  2. 聪明的班主任
  3. 问答
  • 23.76%
  • 65536K

题目描述

GX去高中当班主任了。开学时学校发了很多空白的练习册,GX让每个同学都来领。等大家都回到座位上时,却发现每个同学拿的本数不同。为了避免混乱,他要求同学们坐在位置上,通过传本子使得每个人拿到的本子数量都相同。

为了简化问题,我们假设教室一共有n排,每排有一个同学,已知每个同学手里有$A_i$本书 (1 <= i <= n)。每一秒,班主任可以指挥任意m个同学(1 <= m <= n),让他拿出一本书给相邻的同学。这m个同学给书的过程是同时进行的。

我们想知道最少需要几秒钟,可以让每个同学手里的练习册数量相同。

输入格式

一个整数T,表示有T组样例。

每组样例有两行,第一行一个整数n (1 <= n <= 10000)表示有n个同学。

第二行有n个整数, 表示每个同学手里初始的书本数。(0 <= $A_i$ <= 100000)

输出格式

一个整数,表示最少的秒数,如果无法完成,输出-1。

样例输入

1
5
1 2 3 4 5

样例输出

3

题目来源

北方大学 ACM 多校训练赛 第十四场

想挑战这道题吗

  • main.c