使n个居民点到邮局的距离总和最小。-Read.ppt

邮局选址问题 姓名 ：林 炜 学号 ：060320079 问题描述 在一个按照东西和南北方向划分成规整街区的城市里，n个居民点散乱地分布在不同的街区中。用x 坐标表示东西向，用y坐标表示南北向。各居民点的位置可以由坐标(x,y)表示。 街区中任意2 点(x1,y1)和(x2,y2)之间的距离可以用数值|x1-x2|+|y1-y2|度量。 居民们希望在城市中选择建立邮局的最佳位置，使n个居民点到邮局的距离总和最小。 编程任务 给定n 个居民点的位置,编程计算n 个居民点到邮局的距离总和的最小值。 结果输出 程序运行结束时，将计算结果输出到文件output.txt 中。文件的第1 行中的数是n 个居民点到邮局的距离总和的最小值。 输入文件示例 输出文件示例 input.txt output.txt 5 10 1 2 2 2 1 3 3 -2 3 3 算法分析 首先，给定一个从小到大的数列x1,x2,……，xn,设x是从x1到xn与其绝对差之和最小的数，则显然x位于x1与xn之间。那么，由于x1，xn与它们之间的任意一点的距离之和都相等，且都等于xn-x1，因此接下来可以不考虑x1与xn，而考虑剩下的从x2到x[n-1]的数，同样显然有x必然位于x2和x[n-1]之间，依次类推，最后得出的结论是x就是该数列中间的那个数，或者是中间的那两个数之一，而这个数就是中位数。 结论：数列的中位数就是该数列各个数与其绝对差之和最小的数。 算法复杂度分析 空间复杂性：用一个整型变量n记录居民数量，用两个整型数组x，y来存储居的x坐标与y坐标，所以总的空间复杂性为O(n)。 时间复杂性：读入居民坐标用时O(n)，用平均情况下的线性时间选择算法选择x[n],y[n]的中位数用时O(n)，最后遍历一次x[n]，y[n]求距离总和的最小值用时也为O(n)，所以总的时间复杂性为O(n)。 The EndThank you! * * * * 数据输入 由文件input.txt 提供输入数据。文件的第1 行是居民点数n，1￡n￡10000。接下来n 行是居民点的位置，每行2 个整数x 和y，-10000￡x，y￡10000。 因为任意2 点(x1,y1)和(x2,y2)之间的距离是用数值|x1-x2|+|y1-y2|度量的，那么n个点P1----Pn到邮局地点P（x,y）的距离之和可以表示为： |x1-x|+ |x2-x|+……+|xn-x| + |y1-y|+ |y2-y|+……+|yn-y| 。 这样一来，问题转变为分别求x轴和y轴上的一个点，使得该轴上的其他点坐标与该点坐标的差的绝对值之和最小。 于是问题就变为求解中位数。因为给定一个数列，中位数有这样的性质 ：所有数与中位数的绝对差之和最小。 下面给出简略证明（因为如果证明中位数的性质正确，则该题就可以用求解中位数来解题）：