货物搬运

成绩 0 开启时间 2013年02月21日 星期四 23:02
折扣 0.8 折扣时间 2013年02月28日 星期四 23:02
允许迟交 是 关闭时间 2013年02月28日 星期四 23:02
输入文件 move.in 输出文件 move.out

天地无情人有情，一方有难八方支援！目前灾区最紧缺的就是救灾帐篷，全国各地支援的帐篷正紧急向灾区运送。假设围绕汶川县有环行排列的 n 个救灾帐篷的存储点，每个存储点存有帐篷数量分别是 M1 ， M2 ，…， Mn ，且 S=M1+M2+ … +Mn 必为 n 的倍数。可以在任意一个存储点中任取任意数量的帐篷搬运到相邻的存储点。

现在需要找到一种搬运方法，搬运最少的帐篷使得每个存储点中的帐篷数目相同。

例如： n=5 ，每个存储点帐篷的数量分别为 17 ， 9 ， 14 ， 16 ， 4 。我们进行如下搬运：

（1） 存储点①向存储点②搬运 1 个帐篷；

（2） 存储点①向存储点⑤搬运 4 个帐篷；

（3） 存储点③向存储点②搬运 2 个帐篷；

（4） 存储点④向存储点⑤搬运 4 个帐篷。

搬运帐篷的总数量是 1+4+2+4=11 ，并且可以证明这样的搬运方法是最佳搬运方法。

 

【 输入文件 】

 

第一 行一个整数 n （ n ≤ 10000 ），表示有 n

储存点；第二行 n 个整数（ integer 范围）

表示 n 个存储点中帐篷数量。

【 输出文件 】

一个整数，表示最少搬运的帐篷数量。

【 样例输入 】

5

17 9 14 16 4

【 样例输出 】

11