引入1:货仓选址问题 在X轴上有N个商店，其位置位xi（1<i<N),现需要求将货仓在X轴上某一 点，求货仓建在何处时使得货仓到各商店距离之和最小。 Sum_distance=∑abs(xi-xh) 1<=i<=N；
代码语言：javascript复制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且首尾不相连。 解此类问题的方法(伪码）
代码语言：javascript复制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个点将纸牌圈剪开的表达式。 写的比较直观，自己写的时候没必要。
代码语言：javascript复制 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);
}再换一种方式书写
代码语言：javascript复制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]然后你就会发现
代码语言：javascript复制for(int i=1;i<=N;i )
{
ans =abs(s[i]-s[k]);
}转化为仓库选址问题求解。 所以当S[k]为中位数时ans最小。
