在一维数轴中，给定一组点，寻找一个点距离它们之和最近？
若只有两个点，那么在两点连线中间任意位置。
若有三个点，那么在中间那个点即可。
若有四个点，那么在中间两个点之间连线取一个即可。
......
由此可见，其做法是寻找到 “中位点” 因为可以确保在足够多的两点连线之中（那么到那些连线两端的点 距离之和最短）
问题拓展到二位平面。仍然采取一维数轴的做法，一个点可以视作 x y
那么x y分别考虑即可。
x 取所有二维点横坐标的中间值y 取所有二维点纵坐标的中间值
二维平面的海上有nn只船，每只船所在位置为(X_i,Y_i)(Xi,Yi)，每只船还有一个权值W_iWi，现在他们需要聚在一起商讨捕鱼大业，他们想请你找到一个点使得该点到其他点的带权曼哈顿距离之和最小。带权曼哈顿距离=实际曼哈顿距离*∗权值。
n，x数组，y数组，w数组
一行一个数字表示最小的带权输出最小的带权距离之和
示例1
复制
2,[2,1],[1,1],[1,1]复制
1
本问题在二维问题基础上增加了一个点的权重，那么只需要找到【权重中位点】
对于x方向，先按照x升序排序，不断累加w权重，当累加某个点权重之后，和大于总权重1/2 那么该点为 权重中位点
计算所有点到该点的距离*权重 即为x方向上的最小总和 同理 + y方向上的最小总和
struct point{ int x; int y; int w; }; static bool cmpx(point& a,point& b) { return a.x<b.x; } static bool cmpy(point& a,point& b) { return a.y<b.y; } long long MinimumDistance(int n, int* x, int* y, int* w) { point arr[n]; long long sum_w=0; //初始化各个点 并计算总权重 for(int i=0;i<n;i++) { arr[i].x=x[i]; arr[i].y=y[i]; arr[i].w=w[i]; sum_w+=w[i]; } sum_w/=2;//计算中间值 //先按照 x 的下标进行一个排序 sort(arr,arr+n,cmpx); int index_x=-1; long long sum=0; for(int i=0;i<n;i++) { sum+=arr[i].w; if(sum>sum_w) { index_x=i; break; } } //找到按照x下标排序的中点（加权中点） long long ans=0; for(int i=0;i<n;i++) { ans+=abs(arr[i].x-arr[index_x].x)*arr[i].w;//计算到加权中点的x方向的曼哈顿距离 } //按照 y 的下标进行一个排序 sort(arr,arr+n,cmpy); int index_y=-1; sum=0; for(int i=0;i<n;i++) { sum+=arr[i].w; if(sum>sum_w) { index_y=i; break; } } for(int i=0;i<n;i++) { ans+=abs(arr[i].y-arr[index_y].y)*arr[i].w;//计算到加权中点的y方向的曼哈顿距离 } return ans; }
