基本介紹
- 中文名：帶權中位數
定義,帶權中位數問題,證明（簡）,證明的簡單說明,一些符號的意思,
定義
我們都學過中位數問題，即給定了N個數後，位於第[N/2]的數就是中位數。
帶權中位數問題
而在信息學競賽中，有這樣一類題，給出了若干個排列在一條直線上的點，每個點有一個權值，比如說貨物量、人數什麼的，然後讓我們找出使所有點的貨物、人集合到一個點的總代價最小的位置。我們將會發現，這一類問題實際上就是帶權中位數問題。
例如：
我國蒙古大草原上有 N（N 是不大於 100 的自然數）個牧民定居點 P1（X1，Y1）、P2
（X2，Y2）、 …Pn（Xn，Yn），相應地有關權重為 Wi，現在要求你在大草原上找一點 P（Xp，
Yp），使 P點到任 一點 Pi的距離 Di 與Wi 之積之和為最小。
即求 D=W1*D1+W2*D2+…+Wi*Di+…+Wn*Dn 有最小值
結論：對 x與 y兩個方向分別求解帶權中位數，轉化為一維。
設最佳點 p為點 k，則點 k 滿足：
令 W 為點 k到其餘各點的帶權距離之和，則
sigma( i=1 to k-1) Wi <= W/2
sigma( i=k+1 to n) Wi <= W/2
同時滿足上述兩式的點 k 即為帶權中位數。
證明（簡）
若最優點在T
則有：
∑{D[I]*DIST(I，T)}(I<>T)<=∑{D[I]*DIST(I,T+1)}(I<>T+1)
將此式化為：
∑{D[L]}*DIST(L,T)}+∑{D[R]*DIST(R,T)}+D[T+1]*DIST(T+1,T)
<=∑{D[L]}*DIST(L,T+1)}+∑{D[R]*DIST(R,T+1)}+D[T]*DIST(T,T+1) (L<T&R>T+1)
即：
∑{D[L]*DIST(L,T+1)}-∑{D[L]*DIST(L,T)}(L<T)+D[T]*(DIST(T,T+1))>=∑{D[R]*DIST(R,T)}-∑(D[R]*DIST(R,T+1))(R>T+1)+D[T+1]*(DIST(T,T+1))進一步化簡為：
∑{D[L]*(DIST(L,T)-DIST[L,T+1])}(L<=T)<=∑{D[R]*(DIST(R,T+1)-DIST(R,T))}(R>=T+1)∵DIST(L,T)-DIST(L,T+1)=DIST(T,T+1)
DIST(R,T+1)-DIST(R,T)=DIST(T+1,T)
OBVIOUSLY : DIST(T,T+1)=DIST(T+1,T)
因此：
∑D[L](L<=T)>=∑(D[R])(R>=T+1)
即：∑D[L](L<T)+D[T]>=∑(D[R])(R>T)
因此我們發現，若T是最優點，則必有其左邊的權值和加上D[T]後大於右邊的權值和
而類似的，我們可以證明其右邊的權值和加上D[T]後大於左邊的權值和
因此我們要找的點也就是滿足以上條件的點。注意到此時我們的選擇已經和具體的位置（坐標）沒有關係了，而成為主要考慮因素的僅僅是各點上的權值。
因為左邊的權值和數+D[T]>=右邊的權值和，那么：
LEFTSUM+D[T]>=RIGHTSUM=SUMALL-(LEFTSUM+D[T])
=>2*(LEFTSUM+D[T])>=SUMALL
=>2*RIGHTSUM<=SUMALL
同理可得：
RIGHTSUM+D[T]>=LEFTSUM=SUMALL-(RIGHTSUM+D[T])
=>2*(RIGHTSUM+D[T])>=SUMALL
=>2*LEFTSUM<=SUMALL
此時我們發現：
2*LEFTSUM<=SUMALL 而 2*(LEFTSUM+D[T])>=SUMALL
也即是說當前的位置T上的數包含了第[(SUMALL)/2]個數，由開篇的簡述可知，這第[(SUMALL)/2]個數，就是這個序列中的帶權中位數。所以這一類問題，實質上就是帶權中位數問題。
證明的簡單說明
我們可以簡單地把上面的證明過程看作是左邊的人都集合到了M點，而右邊的人都集合到了M+1點。此時形成了兩軍對壘的形式，如果左邊的總人數比右邊的多，那么從左邊走到右邊去就沒有從右邊走到左邊來優，反之亦然。那么既然在當前點我們左邊的總人數已經比右邊多了，那么再往右邊移動，左邊的人數會進一步增多，而右邊的人會減少，那么只會導致更差的結果，所以此時我們可以判斷最優點一定在當前點的左邊，或者至少在當前這個點。那么範圍就從當前的[L，R]縮小到了[L，M]，通過不斷地縮小範圍（而每一次縮小我們都砍掉了一半的範圍），最後我們得到的將是一個點——那就是我們要求的集合位置。
一些符號的意思
D[I]—第I個點的權值
DIST（I，J）—I到J點的距離，即DIST（I，J）=|NUM[I]-NUM[J]|
由定義式易知：DIST（I，J）=DIST（J，I）
