TZOJ：1310

我们先设x【i】为第i个人给左边的人糖果数量，如果是正数就是给，如果是负数就是拿。

定义pos为糖果的平均数，a数组存储每个人初始的糖果数量

那么就得到这一条恒等式

通过这个恒等式，我们再把i从1到n带入，就得到了n条方程

可以发现其中x【i】都是未知数，如果把他们全部相加会得到没有x数组的一条等式，也就是n条方程只有n-1条是有效的，因此n-1条方程可以解出n-1个未知数，所以就用x【1】去表示其他x。

可以发现

我们的目的是让|x【1】|+|x【2】|+|x【3】|.......+|x【n】|最小

x【i】实际上是一个前缀和，由前面一个状态加上pos-a【j】得到当前状态，所以问题就变成了一堆常数和一个未知数的差值之和怎么样才能更小，这个时候就要用到中位数，只要取到这堆数的中间数作为x【1】的值，那么其他点到这个数的距离之和就是最小的。

虽然放在贪心专题，但我感觉这跟贪心都脱离了，完全是推导出了一个结论，然后通过结论去写。

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e6+10;
int a[N],n,c[N];

signed main()
{
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>n;
	int sum=0;
	for(int i=1;i<=n;i++)cin>>a[i],sum+=a[i];
	int pos=sum/n;
	c[1]=0;
	for(int i=2;i<=n;i++)c[i]=c[i-1]+pos-a[i];
	sum=0;
	sort(c+1,c+1+n);
	for(int i=1;i<=n;i++)
		sum+=abs(c[n/2+1]-c[i]);
	cout<<sum<<endl;
}