51nod 1108

三维空间上有N个点, 求一个点使它到这N个点的曼哈顿距离之和最小,输出这个最小的距离之和。

点(x1,y1,z1)到(x2,y2,z2)的曼哈顿距离就是|x1-x2| + |y1-y2| + |z1-z2|。即3维坐标差的绝对值之和。
Input

Output

Input示例

Output示例

 

首先,对于x,y,z,我们只需要取局部最优

例如x,可以发现,我们找到的点应该是x的中位数。

设x中位数的位置(n+1)/2,(奇数取最中间的数),如果这个点不是最小的,把这个点左边的点作为最小的点,它的距离的绝对值之和一定比当前大(可以画图)

 

 

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注