1、对于x1,x2,...xn的中位数即各xi的带权中位数，此处权值wi=1/n, i=1,2....n
此时x1，x2...xn的中位数为xk，k=┗（n+1）/2┛.则x1,x2...x(k-1)的权值和为┗（n-1）/2┛/n<=(n-1)/2n<1/2
2、通过排序，在O(nlgn)的最坏情况时间内求出n个元素的带权中位数
先用堆排序（按xi的增序）。设排序后的数组为x1，x2...xn.
再用一个数组zw[1,2...n]:
zw[1]=w[1]
for i=2->n
zw[i]=w[i]+w[i-1]
if(zw[n]-zw[i]<=1/2)
resultpos=i
for i=2->n
if(zw[i-1]<1/2 and zw[n]-zw[i]<=1/2)
resultpos=i
3、利用一个线性时间的中位数算法（如SELECT算法），在最坏情况O(n)时间内求出n个数的带权中位数
思想：先用SELECT选出n/2小的元素。由于select中调用了partition，对数组进行了划分，则x1...x(n/2-1)的数都比x(n/2)小，后面的数都比x(n/2)大。统计低区和高区的wi之和。如果满足带权中位数的要求，则此时x(n/2)为所求元素。否则，如果低区的权重之后大于1/2,则对低区递归调用次算法。如果高区的权重大于1/2,则对高区调用此算法。直到找到带权中位数
4、邮局位置问题: 已知n个点p1，p2, ...pn及他们相联系的权重w1,w2....wn,找到一点p（不一定是输入点中的一个），使和式wid(p,pi)最小，此处d(a,b)表示点a和b之间的距离，d(a,b)=|a-b|.
1) 证明带权中位数是一维邮局位置问题的最佳解决方案。其中所有点都是实数。
2) 找出二维邮局位置问题的最佳解答。其中所有点是(x,y),并且(x1,y1)与(x2,y2)距离是Manhattan距离。d(a,b)=|x1-x2|+|y1-y2|
1)证明：采用反证法。假设带权中位数的位置为xk（一定是n个点中的某一个）。并假设最佳位置点为xm，xm=xk+delta(x) (delta(x)可以大于0或者小于0)
直观理解？
2）因为x和y是独立变量，则结果是两个一维的带权中位数的叠加。