帶權(quán)中位數(shù)定義如下：
中位數(shù).jpg)
郵局位置問題定義如下：
上一篇文章輸油管道問題里面證明了，當(dāng)權(quán)值Wi都為1的時(shí)候，中位數(shù)就是最佳的解。但是，現(xiàn)在Wi已經(jīng)不一定是1了。所以，現(xiàn)在
需要證明在任意Wi的取值情況下，帶權(quán)中位數(shù)能夠成為郵局位置的最佳解。假設(shè)，所有Wi都是1的倍數(shù)，如果是小數(shù)的話，可以所有的
Wi都乘以一定的倍數(shù)。那么wi*d(p,pi) =
Σ(p,pi)(i從1到wi)，這個(gè)意思是把距離乘以了wi倍。
但是，現(xiàn)在可以換一種看法，換成了pi位置有wi個(gè)重合的點(diǎn)，且每一個(gè)點(diǎn)的權(quán)值都是1，那么其和也是wi*d(p,pi)。那么對(duì)所有的pi
都這樣分解，就把問題重新轉(zhuǎn)換成了輸油管道問題了。輸油管道問題的最優(yōu)解就是中位數(shù)，那么郵局問題的最優(yōu)解就是轉(zhuǎn)換之后的
這些點(diǎn)的中位數(shù)點(diǎn)。而這個(gè)點(diǎn)一定存在于帶權(quán)中位數(shù)那個(gè)點(diǎn)分解出的一堆點(diǎn)中。
二維郵局問題的解法是把x和y分開求2次一維郵局問題，然后把解組和起來，得到答案。
求帶權(quán)中位數(shù)的算法比較簡(jiǎn)單，直接的做法是，先把n個(gè)點(diǎn)按照位置排序，然后按點(diǎn)的位置從小到大遍歷，找到滿足要求的點(diǎn)即可。
不算排序點(diǎn)位置的預(yù)處理，因?yàn)楹芏鄷r(shí)候點(diǎn)應(yīng)該就是按順序給出的，所以其時(shí)間復(fù)雜度是O(n)。
要求：中位數(shù)公式.jpg)