因为昨天模拟赛考了这个题，并且爆 0 了，所以应当为此题写一篇题解。

题意

有 $n$ 个小朋友坐成一圈，每人有 $a_i$ 个糖果。每人只能给左右两人传递糖果。每人每次传递一个糖果代价为 $1$ 。求使所有人获得均等糖果的最小代价。 $n\le10^6$ 。

点击查看题解

题解

思路 1

环形均分纸牌。P1031 [NOIP2002 提高组] 均分纸牌。

一般的均分纸牌问题就相当于在第 $n$ 个人与第 $1$ 个人之间把环断开，此时这 $n$ 个人站成一行，第 $i$ 人持有的纸牌数、前缀和分别是 $a_i$ ， $s_i$ 。设 $ans$ 为答案。设 $x$ 为平均数。~~不在上面加横杠了，因为懒~~。

如果在第 $k$ 个人之后把环断开站成一行，则：

$\forall i\in[k+1,n]$ ，第 $i$ 个人持有的数目的前缀和是 $s_{i}-s_k$ 。
$\forall i\in[1,k]$ ，第 $i$ 个人持有的数目的前缀和是 $s_i+s_{n}-s_k$ 。

我们考虑整体和隔离的思想。回到一般的均分纸牌问题，将前 $i$ 个看做一个整体，显然前 $i$ 个内部的均分是不会改变其整体结构的，因而对于该体系来说，想要达到平均结构，就必须与下一个体系交换足够的纸牌，而交换数量就是 $|s_i - ix|$ ，然后就可以推出一个结论：

ans=\sum\limits_{i=1}^n |s_i-ix|

也就是将每次体系更新的贡献加起来。

若设 $a_i'=a_i-x$ ， $s_i'$ 是 $a_i'$ 的前缀和，则：

s_i'=s_i-ix

结合上面的式子，得：

ans=\sum\limits_{i=1}^n |s_i'|

这就是均分纸牌问题的通用公式。

对于环形问题，首先考虑切开。因为 $s_i'=s_i-ix$ ，所以 $s_n'=0$ 。所以 $s_i'$ 前缀和的变化仅仅是减去 $s_k'$ 。所以，所需最小花费为：

\sum\limits_{i=1}^{n}|s_i'-s_k'|

那么，现在是要找到一个 $s_k'$ ，使得上面的式子的值最小。显然， $s_k'$ 就是 $s'$ 数列的中位数（由于思路 2 也要用到这个结论，所以证明在思路 2）。

所以就做完了。找第 $k$ 大的数存在 $O(n)$ 算法，所以时间复杂度为 $O(n)$ 。

思路 2

显然，要使每个人获得均等糖果，每个人的糖果数应为 $x$ 。设第 $i$ 个人需向右传 $b_i$ 个糖果，对于第 $i$ 个人易得式子：

\begin{cases} a_i+b_{i-1}-b_i=x & i\in[2,n] \\\\ a_i+b_n-b_i=x & i=1 \end{cases}

变形得：

b_i=\begin{cases} a_i+b_{i-1}-x & i\in[2,n] \\\\ a_i+b_n-x & i=1 \end{cases}

$\forall i\in[2,n]$ ，展开递推式，得：

b_i=b_1+\sum\limits_{j=2}^i(a_j-x)

b_i=b_1+s_i-s_1-x(i-1)

设 $c_i=s_1-s_i+x(i-1)$ ，则得：

b_i=b_1-c_i

题目要求最小化：

\sum\limits_{i=1}^n |b_i|

即：

\sum\limits_{i=1}^n |b_1-c_i|

那么，至少预处理所有 $c_i$ 是可以 $O(n)$ 的。现在是要找到一个 $b_1$ ，使得上面的式子的值最小。显然， $b_1$ 就是 $c$ 数列的中位数。

证明：把每个 $c_i$ 对应到数轴上。设 $\forall i\in[1,n],j=n-i+1$ 。对 $c_i$ 和 $c_j$ 两两配对。那么对于每个数对 $(c_i,c_j)$ ，两者距离最小值一定是 $|c_i-c_j|$ （两点之间线段最短）。则在数轴上， $b_1$ 可以选择在 $c_i$ ， $c_j$ 中间。这样，考虑每个数对，最后易得 $b_1$ 就是 $c$ 数列的中位数。由于 $|c_i-c_j|=|c_i-b_1|+|b_1-c_j|$ ，易得其正确性。

所以就做完了。找第 $k$ 大的数存在 $O(n)$ 算法，所以时间复杂度为 $O(n)$ 。

代码

#include<bits/stdc++.h>
using namespace std;
namespace _yz
{
	typedef long long ll;
	const ll N=1000000+10;
	ll n,a[N],s[N],c[N],x,mid,ans=0;
	void solve1()
	{
		for(ll i=1;i<=n;i++) a[i]-=x;
		for(ll i=1;i<=n;i++) s[i]=s[i-1]+a[i];
		nth_element(s+1,s+mid,s+1+n);
		//nth_element(i,j,k,l)
		//i,j,k 都是迭代器。在 [i,k) 区间内进行重排，
		//使得比 j 大的和比 j 小的以 j 为分界分开。
		//此时第 j 大的元素刚好是第 j 个元素。 
		//l 是自定义函数，判断大小。 
		for(ll i=1;i<=n;i++)
			ans+=abs(s[i]-s[mid]);
	}
	void solve2()
	{
		for(ll i=1;i<=n;i++) s[i]=s[i-1]+a[i];
		for(ll i=1;i<=n;i++) c[i]=s[1]-s[i]+x*(i-1);
		nth_element(c+1,c+mid,c+1+n);
		for(ll i=1;i<=n;i++)
			ans+=abs(c[i]-c[mid]);
	}
	void yzmain()
	{
		scanf("%lld",&n);
		for(ll i=1;i<=n;i++)
		{
			scanf("%lld",a+i);
			x+=a[i];
		}
		x/=n;mid=(1+n)/2;
		solve2();
		printf("%lld\n",ans);
		return;
	}
}
int main()
{
	//freopen("in.txt","r",stdin);
	//freopen("out.txt","w",stdout);
	_yz::yzmain();
	return 0;
}