万箭穿逼
范文一：中位数的应用
中位数应用，那些未指明权值的默认权值为1，定义+例题，看完别说你还不懂！！！
中位数，编程问题中即n/2位置处的数，主要用的是带权中位数，带权中位数（Weighted Median），
其定义和中位数的差别在于：
中位数：n个元素集合中，第n/2小的元素。
带权中位数：对于n个互不相同的元素集合x1、x2……xn，其权重依次为w1、w2……wn。令W =
sigma(wi)，则带权中位数xk满足：
sigma(wi)(xi
sigma(wi)(xi>xk)<=w>
其中sigma表示求和。
带权中位数xk满足：sigma(|xi-xk|*wi)最小。
应用一：
仓库选址
★问题描述
在一个直线的公路上，有n个连锁超市，为了便于物流管理，物流公司决定在公路上
建立一个仓库，为这些超市供货。
已知n个超市在公路上的坐标依次为x1, x2, …, xn，每天需要的货物数量依次为w1, w2,
…, wn, 假设在公路上坐标为xp的地点建立仓库，那么仓库为超市的供货费用依次为w1*|x1-xp|,
w2*|x2-xp|, …, wn*|xn-xp|。
★编程任务
在公路上选择一个位置xp建立仓库，使得仓库为超市供货的总费用最小。
★数据输入
由文件input.txt提供输入数据。输入第一行为一个整数n，表示公路上超市的个数。接下
来n行，每行两个整数表示xi和wi。(1 ≤ n，xi，wi ≤ 1,000,000)
★数据输出
将程序运行结果输出到文件output.txt中。输出一行一个整数，表示仓库每天为超市供
货的最小费用。
view plaincopy to clipboardprint?
1. input:
2.
3. 3
4. 1 3
5. 2 2
6. 3 1
7.
8. output:
9.
10. 4
11. 解法：
12. 将输入的数据按x排序，若x相等则按需要货物的多少排序，结构体内重载了<运算符。然后寻找所谓>
13.
14. 的带权中位数，即***语句，然后计算最小费用。
15. code:
16. #include
17. #include
18. #include
19. using namespace std;
20. const int nax=10010;
21. int coun=0;
22. int label[2*nax];
23. typedef struct sd
24. {
25. int x;
26. int v;
27. bool operator<(const struct="" sd="" &tmp)="" const//从小到大排="">
28. {
29. if(x< span="">return true;
30. if(x>tmp.x) return false;
31. return v< span="">
32. };
33. }pzj;
34. pzj pzjay[nax];
35. int main()
36. {
37. int n,i,suma=0,sumb=0;
38. scanf("%d",&n);
39. for(i=0;i< span="">
40. {
41. scanf("%d%d",&pzjay[i].x,&pzjay[i].v);
42. suma+=pzjay[i].v;
43. }
44. sort(pzjay,pzjay+n);
45. for(i=0;sumb+pzjay[i].v<>//***
46. sumb+=pzjay[i].v;
47. int ans=0;
48. while(n--)
49. ans+=abs(pzjay[n].x-pzjay[i].x)*pzjay[n].v;
50. printf("%d\n",ans);
51. }
input: 3 1 3 2 2 3 1 output: 4 解法： 将输入的数据按x排序，若x相等则按需要货物的多少排序，结构体内重载了<运算符。然后寻找所谓 的带权中位数，即***语句，然后计算最小费用。="" code:="">
