Description

　　圆桌上坐着n个人，每人有一定数量的金币，金币总数能被n整除。每个人可以给他左右相邻的人一些金币，最终使得每个人的金币数目相等。你的任务是求出被转手的金币数量的最小值。

Input

　　第一行为整数n（n>=3），以下n行每行一个正整数，按逆时针顺序给出每个人拥有的金币数。

Output 

　　输出被转手金币数量的最小值。

Sample Input

4

1

2

5

4

Sample Output

4

　　样例解释

　　设四个人编号为1,2,3,4。第3个人给第2个人2个金币（变成1,4,3,4），第2个人和第4个人分别给第1个人1个金币。

HINT

　　N<=100000,总金币数<=10^9

Source

Solution

　　同，数据范围还小了不少，，，

1 #include 
      
        2 using namespace std; 3 long long a[100005], s[100005]; 4 int main() 5 { 6     int n; 7     long long ave = 0, ans = 0; 8     scanf("%d", &n); 9     for(int i = 1; i <= n; ++i)10         scanf("%lld", a + i);11     for(int i = 1; i <= n; ++i)12         ave += a[i];13     ave /= n;14     for(int i = 1; i <= n; ++i)15         s[i] = s[i - 1] + a[i] - ave;16     sort(s + 1, s + n + 1);17     for(int i = 1; i < n / 2 + 1; ++i)18         ans += s[n / 2 + 1] - s[i];19     for(int i = n / 2 + 1; i <= n; ++i)20         ans += s[i] - s[n / 2 + 1];21     printf("%lld\n", ans);22     return 0;23 }