引入1:貨倉選址問題
在X軸上有N個商店，其位置位xi（1<i<N),現(xiàn)需要求將貨倉在X軸上某一 點，求貨倉建在何處時使得貨倉到各商店距離之和最小。
Sum_distance=∑abs(xi-xh) 1<=i<=N；

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

假設(shè)建在中位數(shù)xm處的距離Sum_distance=SUM，則建在xm-1的位置處的，中位數(shù)左側(cè)的每個abs都減小1，中位數(shù)右側(cè)的每個數(shù)都增加1，中位數(shù)左側(cè)與右側(cè)的個數(shù)相同，則左右抵消，若中位數(shù)xm的個數(shù)有w個則Sum_distance=SUM+w>SUM;因此建立在中位數(shù)處的距離和最小得證。
引入2：均分紙牌問題
有N個人坐在一起成一條直線，每個人手中有xi張牌 1<=i<=N，每個每次只能傳遞一張紙牌給左邊或者右邊的人,請問至少傳遞多少次使得每個人手中的牌數(shù)相等，假設(shè)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；//答案

最終章:環(huán)形均分紙牌問題
有N個人坐在一起成一個圈，每個人手中有xi張牌 1<=i<=N，每個每次只能傳遞一張紙牌給左邊或者右邊的人,請問至少傳遞多少次使得每個人手中的牌數(shù)相等，假設(shè)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為操作后的 設(shè)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]

然后你就會發(fā)現(xiàn)

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

轉(zhuǎn)化為倉庫選址問題求解。
所以當S[k]為中位數(shù)時ans最小。

總結(jié)

以上是生活随笔為你收集整理的环形均分纸牌问题（中位数)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。