OI题库

【题目描述】

老师准备了一堆糖果，恰好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范围内．

【来源】

在此键入。