算法求助！急！

来源：百度知道 编辑：UC知道 时间：2024/05/29 05:36:51
有n（n<=10000）个村庄在一条直线上，给定坐标（-10000到10000），一个坐标上可能有多个村庄。现在要在路上设一个商店（不一定在某一个有村庄的点），使得所有村庄到这个商店的距离之和最小，求这个最小距离。

要的是算法，不是代码，越详细越好。很急，多谢大牛们

如果是奇数，设在中间的点上，如果是偶数，在中间两个点间的任意位置

假设该商店的坐标是a，每个村庄的坐标是n(i),那么每个村庄到商店的距离是可以算出来的，abs(a-n(i)),这样，这个算法就是计算所有距离之和的最小值。
如果要实现，那么这个n值是要确定的，然后用随机数生成每个村庄的坐标值（可以重复），这也是确定的。这样一来，就可以通过最简单的循环来从头到尾测试商店的每个可能的位置，并且计算距离的总和，把这个总和进行比较，最后就可以得到最合适的位置。

ACM的题？哪个OJ上的
方法如下：
设最左边的点位置是0，这样每个村庄都有位置了(相对于-10000的距离），算一下所有位置的加权平均值，再加-10000就是那个商店位置。然后就可以计算总距离了。
这样肯定没有错，不过没有证明。有兴趣可以自己尝试一下。