邮局选址问题 - Xredman - 博客园
在一个按照东西和南北方向划分成规整街区的城市里，n个居民点散乱地分布在不同的街区中。用x 坐标表示东西向，用y坐标表示南北向。各居民点的位置可以由坐标(x,y)表示。街区中任意2 点(x1,y1)和(x2,y2)之间的距离可以用数值|x1-x2|+|y1-y2|度量。居民们希望在城市中选择建立邮局的最佳位置，使n个居民点到邮局的距离总和最小。
编程任务：
给定n 个居民点的位置,编程计算n 个居民点到邮局的距离总和的最小值。
每组测试数据输入的第1 行是居民点数n，1≤n≤10000。接下来n 行是居民点的位置，每行2 个整数x 和y，-10000≤x，y≤10000。
那么：
邮局的x坐标只与n个居民点的x坐标相关；
邮局的y 坐标只与n个居民点的y坐标相关；
下面以求x坐标为例，y坐标的求法类似;
假设对n个居民点的x坐标按大小排序后为x1,x2....xi...xn;
对x1,xn两点来说，最近的点肯定在x1,xn之间，且跟两点的距离和==xn-x1；
对x2,x(n-1)两点来说，最近的点肯定在x2,x(n-1)之间,且跟两点的距离和==x(n-1)-x2；
....
所以若n为奇数，则邮局的x坐标取最中间的值时最小；
所以若n为偶数，则邮局的x坐标可以取最中间两个值的之间的任意值;
最终公式：x=(x(n/2+1)+x(n/2+2)+...+xn)-(x1+x2+..+x(n/2))
最终公式：
s=(x(n/2+1)+x(n/2+2)+...+xn)-(x1+x2+..+x(n/2))
+(y(n/2+1)+y(n/2+2)+...+yn)-(y1+y2+..+y(n/2))
bool cmp(int a, int b)
{
if(a < b)
return true;
else
return false;
}
int cal(int str[], int n)
{
int sum = 0,i,mid;
mid = str[n / 2];
for(i = 0; i < n; i++)
sum += abs(str[i] - mid);
return sum;
}
int main()
{
int x[MAX_SIZE],y[MAX_SIZE];
int i, n;
while(scanf("%d",&n) != EOF)
{
for(i = 0; i < n; i++)
scanf("%d%d",x + i, y + i);
sort(x ,x + n, cmp);
sort(y, y + n, cmp);
printf("%d\n",cal(x, n) + cal(y, n));
}
return 0;
}
http://segmentfault.com/a/1190000000636173
在一个按照东西和南北方向划分成规整街区的城市里，n个居民点散乱地分布在不同的街区中。用x 坐标表示东西向，用y坐标表示南北向。各居民点的位置可以由坐标(x,y)表示。街区中任意2 点(x1,y1)和(x2,y2)之间的距离可以用数值|x1-x2|+|y1-y2|度量。居民们希望在城市中选择建立邮局的最佳位置，使n个居民点到邮局的距离总和最小。
编程任务：
给定n 个居民点的位置,编程计算n 个居民点到邮局的距离总和的最小值。
Input
输入由多组测试数据组成。 每组测试数据输入的第1 行是居民点数n，1≤n≤10000。接下来n 行是居民点的位置，每行2 个整数x 和y，-10000≤x，y≤10000。
Output
对应每组输入，输出的第1 行中的数是n 个居民点到邮局的距离总和的最小值。
Sample Input
5 1 2 2 2 1 3 3 -2 3 3
Sample Output
10
因为街区中任意2 点(x1,y1)和(x2,y2)之间的距离可以用数值 |x1-x2 |+ |y1-y2 |度量； 那么：
邮局的x坐标只与n个居民点的x坐标相关；
邮局的y 坐标只与n个居民点的y坐标相关；
下面以求x坐标为例，y坐标的求法类似;
假设对n个居民点的x坐标按大小排序后为x1,x2....xi...xn;
对x1,xn两点来说，最近的点肯定在x1,xn之间，且跟两点的距离和==xn-x1；
对x2,x(n-1)两点来说，最近的点肯定在x2,x(n-1)之间,且跟两点的距离和==x(n-1)-x2；
....
所以若n为奇数，则邮局的x坐标取最中间的值时最小；
所以若n为偶数，则邮局的x坐标可以取最中间两个值的之间的任意值;
最终公式：x=(x(n/2+1)+x(n/2+2)+...+xn)-(x1+x2+..+x(n/2))
最终公式：
s=(x(n/2+1)+x(n/2+2)+...+xn)-(x1+x2+..+x(n/2))
+(y(n/2+1)+y(n/2+2)+...+yn)-(y1+y2+..+y(n/2))
bool cmp(int a, int b)
{ if(a < b) return true; else return false;}int cal(int str[], int n){ int sum = 0,i,mid; mid = str[n / 2]; for(i = 0; i < n; i++) sum += abs(str[i] - mid); return sum;}int main(){ int x[MAX_SIZE],y[MAX_SIZE]; int i, n; while(scanf("%d",&n) != EOF) { for(i = 0; i < n; i++) scanf("%d%d",x + i, y + i); sort(x ,x + n, cmp); sort(y, y + n, cmp); printf("%d\n",cal(x, n) + cal(y, n)); } return 0;}http://segmentfault.com/a/1190000000636173
因为任意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轴上的一个点，使得该轴上的其他点坐标与该点坐标的差的绝对值之和最小。
于是问题就变为求解中位数。因为给定一个数列，中位数有这样的性质 ：所有数与中位数的绝对差之和最小。
下面给出简略证明（因为如果证明中位数的性质正确，则该题就可以用求解中位数来解题）：
这样一来，问题转变为分别求x轴和y轴上的一个点，使得该轴上的其他点坐标与该点坐标的差的绝对值之和最小。
于是问题就变为求解中位数。因为给定一个数列，中位数有这样的性质 ：所有数与中位数的绝对差之和最小。
下面给出简略证明（因为如果证明中位数的性质正确，则该题就可以用求解中位数来解题）：
首先，给定一个从小到大的数列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就是该数列中间的那个数，或者是中间的那两个数之一，而这个数就是中位数。
结论：数列的中位数就是该数列各个数与其绝对差之和最小的数。