题意简述：
有n个小朋友坐成一圈,每人有$a[i]$个糖果每人只能给左右两人传递糖果,每人每次传递一个糖果代价为1,求使所有人获得均等糖果的最小代价
输入格式：
第一行输入一个正整数$n$,表示小朋友的个数
接下来$n$行，每行一个整数$a[i]$,表示第$i$个小朋友初始得到的糖果的颗数
输出格式：
输出一个整数表示最小代价
数据范围：
$1\leq n\leq 1000000$
题解：
该题即为环形均分纸牌问题,是一道比较数学的题目
我们首先定义$a_{i}$为第$i$个人所有的糖果数,所有人糖果数之和为$sum$,不难发现题目若有解那么$\frac{sum}{n}$一定是整数,这样最后每个人的糖果数都要为$\frac{sum}{n}$,那么我们不妨实现先把$a$数组都减去$\frac{sum}{n}$,这样最后要使每个人糖果数都为0
接下来我们定义$x_{i}$为第$i$个人给第$i-1$个人的糖果数,正数即为$i$给$i-1$,负数即为$i-1$给$i$,特别的$x_{1}$表示第1个人给第$n$个人的糖果数,那么我们可以得到以下式子：
$a_{1}-x_{1}+x_{2}=0$
$a_{2}-x_{2}+x_{3}=0$
$a_{3}-x_{3}+x_{4}=0$
$\cdots\cdots\cdots\cdots\cdots$
$a_{n}-x_{n-1}+x_{1}=0$
总共有$n$个变量和$n$个未知数,理论上是可以用高斯消元之类的方法进行求解的,但实际上由前$n-1$个式子可以推出第$n$个式子,所以其实只有$n-1$个式子,但我们要求的是$\sum_{i=1}^n{x_{i}}$的最小值,那么我们可以把所有的$x$都用$x_{1}$来表示进行求解
由上面的式子不难整理出：
$x_{2}=x_{1}-a_{1}$
$x_{3}=x_{2}-a_{2}=(x_{1}-a_{1})-a_{2}=x_{1}-(a_{1}+a_{2})$
$x_{4}=x_{3}-a_{3}=\cdots =x_{1}-(a_{1}+a_{2}+a_{3})$
$\cdots\cdots\cdots\cdots\cdots$
通过这种类似于数学中累加的方式,我们可以得到公式:
$x_{n}=x_{1}-(a_{1}+a_{2}+\cdots +a_{n-1})$
不妨设$s_{n}=\sum_{i=1}^{n}{a_{i}}$
那么答案$\sum_{i=1}^n{x_{i}}=\mid x_{1}\mid+\mid x_{1}-s_{1}\mid+\mid x_{1}-s_{2}\mid+\cdots+\mid x_{1}-s_{n-1}\mid$
这样这道题就可以转化为货仓选址问题,即为在数轴上有$0,s_{1},s_{2}\cdots s_{n-1}$这$n$个点,我们要找到一个$x_{1}$使得到这$n$个货仓的距离最短,显然结论是$x_{1}$的取值为这$n$个数的中位数,那么这道题就解决了,只需要一次排序,时间复杂度为$O(n logn)$
AC代码：
|
|