[HAOI2008]糖果传递

Grade Open Time Friday, 19 September 2014, 10:07 am
Discount 0.8 Time Discount Friday, 26 September 2014, 10:07 am
Allow late Yes Close Time Friday, 26 September 2014, 10:07 am
Input file candya.in Output file candya.out

【题目描述】

老师准备了一堆糖果,恰好n个小朋友可以分到数目一样多的糖果.老师要n个小朋友去拿糖果,然后围着圆桌坐好,第1个小朋友的左边是第n个小朋友其他第i个小朋友左边是第i-1个小朋友。大家坐好后,老师发现,有些小朋友抢了很多的糖果,有的小朋友只得到了一点点糖果,甚至一颗也没有,设第ai个小朋友有ai颗糖果.小朋友们可以选择将一些糖果给他左边的或者右边的小朋友,通过”糖果传递”最后使得每个小朋友得到的糖果数是一样多的,假设一颗糖果从一个小朋友传给另一个小朋友的代价是1,问怎样传递使得所耗的总代最小。

【输入格式】

输入文件第一行一个正整数n,表示小朋友的个数.

接下来n行,每行一个整数ai,表示第i个小朋友得到的糖果的颗数.

【输出格式】

输出只有一个数,表示最小代价

【样例输入】

4

1

2

5

4

【样例输出】

4

【提示】

30%的测试数据,n<=1000

100%的测试数据,n<=1000000.

ai>=0,保证ai在长整型范围内, ai的总和在

int64/long long范围内.

【来源】

在此键入。