比赛场次 47
比赛名称 20091026
比赛状态 已结束比赛成绩
开始时间 2009-10-26 19:00:00
结束时间 2009-10-26 22:00:00
开放分组 全部用户
注释介绍
题目名称 货物搬运
输入输出 move.in/out
时间限制 1000 ms (1 s)
内存限制 128 MiB
测试点数 10 简单对比
用户 结果 时间 内存 得分
Gravatarybh AAAAAAAATA 0.000 s 0.00 MiB 90
Gravatarreamb WAWWWWWWWA 0.000 s 0.00 MiB 20
GravatarHamster WAWWWWWWWA 0.000 s 0.00 MiB 20
GravatarReimBurSe. WAWWWWWWWA 0.000 s 0.00 MiB 20
GravatarAchilles C 0.000 s 0.00 MiB 0

货物搬运

★   输入文件:move.in   输出文件:move.out   简单对比
时间限制:1 s   内存限制:128 MiB

【题目描述】

天地无情人有情,一方有难八方支援!目前灾区最紧缺的就是救灾帐篷,全国各地支援的帐篷正紧急向灾区运送。

假设围绕汶川县有环行排列的 $n$ 个救灾帐篷的存储点,每个存储点存有帐篷数量分别是 $m_1,m_2,\cdots,m_n$ ,且$s=m_1+m_2+\cdots+m_n$必为 $n$ 的倍数。

可以在任意一个存储点中任取任意数量的帐篷搬运到相邻的存储点。现在需要找到一种搬运方法,搬运最少的帐篷使得每个存储点中的帐篷数目相同。

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

(1) 存储点①向存储点②搬运 1 个帐篷;

(2) 存储点①向存储点⑤搬运 4 个帐篷;

(3) 存储点③向存储点②搬运 2 个帐篷;

(4) 存储点④向存储点⑤搬运 4 个帐篷。

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

【输入格式】 

第一行一个整数$n(n\leq 10000)$,表示有$n$个储存点。

第二行 $n$ 个整数(int范围),表示 $n$ 个存储点中帐篷数量。

【输出格式】

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

【输入样例】

5
17 9 14 16 4

【输出样例】

11