Description:


有n个小朋友坐成一圈,每人有ai个糖果。每人只能给左右两人传递糖果。每人每次传递一个糖果代价为1。

Input:


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

Output:


求使所有人获得均等糖果的最小代价。

Sample Input:


Sample Output


题解:


见到n的范围我觉得有一点不科学……
其实n的范围应该是1000000

然后我就开始想怎样贪心,想了一个下午没有一点思绪。
貌似不可行啊。

晚上数论大佬告诉我这是训练指南上的一道原题[摊手],而且还是排在最前面的。
我一年前都在干什么(<-.<-)

然后训练指南告诉我要列方程,于是我就开始列方程。

如果第i个人给第i+1个人a个糖果,然后第i+1个人又给第i个人b个糖果显然是不够优的。
所以我们设 \(x_i\) 表示第 \(i-1\) 个人给第 \(i\) 个人多少个糖果,如果为负数就是反过来, \(x_1\) 表示第 \(n\) 个人给第 \(1\) 个人的糖果数。
我们需要最小化 \(\sum_{i=1}^n \left| x_i \right|\)
有方程组:(其中 \(v\) 表示平均数)

发现最后一个方程是多余的。
我们可以推出:

\[x_i = x_1+\sum_{j=1}^{i-1} a_i - (i-1)v,i = 2,3,\dots,n\]

\(c_i = (i-1)v - \sum_{j=1}^{i-1}a_i\)
我们需要最小化:

\[\sum_{i=1}^n \left| x_1-c_i \right|\]

直接找中间的 \(c_i\) 就可以了。