货物搬运

成绩 0 开启时间 2013年02月21日 星期四 18:02
折扣 0.8 折扣时间 2013年02月28日 星期四 18:02
允许迟交 关闭时间 2013年02月28日 星期四 18: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