『算法-ACM 竞赛』环形均分纸牌问题（中位数)

引入 1:货仓选址问题
在 X 轴上有 N 个商店，其位置位 xi（1<i<N),现需要求将货仓在 X 轴上某一 点，求货仓建在何处时使得货仓到各商店距离之和最小。
Sum_distance=∑abs(xi-xh) 1<=i<=N；

for(int i=1;i<=N;i++)
{
	ans=abs(x[i]-xh);
}

假设建在中位数 xm 处的距离 Sum_distance=SUM，则建在 xm-1 的位置处的，中位数左侧的每个 abs 都减小 1，中位数右侧的每个数都增加 1，中位数左侧与右侧的个数相同，则左右抵消，若中位数 xm 的个数有 w 个则 Sum_distance=SUM+w>SUM;因此建立在中位数处的距离和最小得证。
引入 2：均分纸牌问题
有 N 个人坐在一起成一条直线，每个人手中有 xi 张牌 1<=i<=N，每个每次只能传递一张纸牌给左边或者右边的人,请问至少传递多少次使得每个人手中的牌数相等，假设 SUM=∑xi=K*N 且首尾不相连。
解此类问题的方法(伪码）

SUM=∑x[i]  1<=i<=N, ave=SUM/N;
for(int i=1;i<=N-1;i++)
{
	x[i+1]=x[i]-ave;
	ans=abs(x[i]-ave);
}
retrun ans；//答案

最终章:环形均分纸牌问题
有 N 个人坐在一起成一个圈，每个人手中有 xi 张牌 1<=i<=N，每个每次只能传递一张纸牌给左边或者右边的人,请问至少传递多少次使得每个人手中的牌数相等，假设 SUM=∑xi=K*N 且首尾相连。
对于此种问题，我们先给出朴素算法，无论怎样交换最后都会有两个人不会交换（看引入二）则可以理解为在某处讲指牌圈剪开，再进行线性均分纸牌，也就是同过枚举剪开的位置，进而不断更新 ans 即可。
但是我们写出在第 m 个点将纸牌圈剪开的表达式。
写的比较直观，自己写的时候没必要。

 for(int i=m;i<=n-1;i++
 {
 	x[i+1]+=x[i]-ave;
ans+=abs(x[i]-ave);
 }
   x[1]+=x[n]-ave;
ans+=abs(x[n]-ave);
  for(int i=1;i<m-1;i++
 {
 	x[i+1]+=x[i]-ave;
ans+=abs(x[i]-ave);
 }

再换一种方式书写

for(int i=1;i<=N-1;i++)
{x[i]-=ave;}
for(int i=m;i<=n-1;i++
{
	x[i+1]+=x[i];
	ans+=abs(x[i]);
}
x[1]+=x[n];
ans+=abs(x[n]);
for(int i=1;i<m;i++)
{
	x[i+1]+=x[i];
	ans+=abs(x[i]);
}
则ans=abs(X[m])+abs(X[m+1])+……+abs(X[n])+abs(X[1])+……+abs(X[m-1]) //大X为操作后的
设s[i]为前i项和
X[m]=x[m]=s[m]-s[k-1]
X[m+1]=x[m]+x[m+1]=s[m+1]-s[k-1]
……
X[n]=x[m]+……+x[n]=s[n]-s[m-1]
X[1]=x[m]+……+x[n]+x[1]=s[n]+s[1]-s[m-1]
X[2]=x[m]+……+x[n]+x[1]+x[2]=s[n]+s[2]-s[m-1]
X[m-1]=x[m]+……+x[n]+x[1]+x[2]+……+x[m-2]=s[n]+s[m-1]-s[m-1]

然后你就会发现

for(int i=1;i<=N;i++)
{
	ans+=abs(s[i]-s[k]);
}

转化为仓库选址问题求解。
所以当 S[k]为中位数时 ans 最小。