小白算法练习 街区最短问题

描述一个街区有很多住户，街区的街道只能为东西、南北两种方向。

住户只可以沿着街道行走。

各个街道之间的间隔相等。

用(x,y)来表示住户坐在的街区。

例如（4,20），表示用户在东西方向第4个街道，南北方向第20个街道。

现在要建一个邮局，使得各个住户到邮局的距离之和最少。

求现在这个邮局应该建在那个地方使得所有住户距离之和最小；

输入

第一行一个整数n<20，表示有n组测试数据，下面是n组数据;
每组第一行一个整数m<20,表示本组有m个住户，下面的m行每行有两个整数0<x,y<100，表示某个用户所在街区的坐标。
m行后是新一组的数据；

输出

每组数据输出到邮局最小的距离和，回车结束；

样例输入

2
3
1 1
2 1
1 2
5
2 9 
5 20
11 9
1 1
1 20

样例输出

2
44

思路

我相信许多和我一样的小白都是不会马上有什么现成的算法或是思路跳出来，那我们是来解决问题的，我们要考虑我们要求的是什么，我们有哪些条件？

条件：若干个地点Xi的坐标（xi，yi）

求解：求一个地点A的坐标（Xa，Ya）

解的要求：A到所有Xi的哈曼顿距离最小（哈曼顿距离是什么可以在我文章的各种距离和python实现中看到，或者百度）

最初的考虑

那么我们首先来说说最小白的我，看到这题目有什么想法：根据解的要求我们知道求的是所有 | Xi-Xa | 的和 与 所有 | Yi-Ya | 的和。xi，yi是全部已知的，未知的只是A的坐标（Xa，Ya）而已。对吗！既然我们只有两个未知参数那就好办了，我们让两个未知参数不停的变换，那么最后的距离肯定是不断变化的。假如坐标（Xa，Ya）=（0，0）他对应一个距离值Z1，（Xa，Ya）=（100，100）也对应一个距离值Z2，我们需要把所有在（0，0）到（100，100）的距离值都算出来再逐一比较，得出最小的不就行了吗？

出现了问题

但我们发现这样好像速度太慢了，如果坐标的范围不是0-100而是0-10000呢，上面的方法显然有点不够用了，对吗！那么我们肯定想0-100的点能不能减少呢？那么我们才开始思考下面的问题，下面的想法才是我们应该去学习的，一步一步锻炼自己动脑的能力，而不是遇到问题去查用什么现成的动规啊什么的算法。当然我们最后肯定要去看一些好的源代码，去思考别人是怎么想的，如果一开始就有思路的话，站在前任人的肩膀上也是件好事

减少了一些计算量

我在纸上画了一个坐标轴，上面画了这几个点，

1 1
3 1
2 2

那我们还要求（100，100）到这几个点的距离吗，完全没必要，我们会发现这三个点X在1-3之间那么Xa也应该在1-3之间，Y在1-2之间，Ya也应该在1-2之间，为什么呢？我是画图之后发现的。那么我们来思考这样的问题 — — 我们先把Y定死，只有X动，我们会取哪里的数呢？这我就不多说了，所以肯定在最小值到最大值的范围内咯。你可以看一下图（黄色），一下子就明白了。

然后我们更具上面定y动x，我们会发现当我们取A的坐标是Xi的某一个点的坐标时，这个值是最小的。为什么呢？因为你把Y定死了（黄线），X在这个区间中取值，在这个区间中取值，当Xa=最中间的点的x时距离最小，希望你能理解，看图，比较好理解。那么对于所有的Y只有在这条紫色的线上才可能取到最小值，那么这时候考虑紫线上上面时候最小，应该是在X轴交点上最小，那么下面开始写代码，有思路就好写代码了呀。

那么我们只要求 横坐标的最中间点的坐标和 纵坐标的最中间点的坐标 。我在很多博客上看到，他们说是中位数，我感觉有歧义，更好的说法是中间点的那个数。

#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
int main(){
int n;//多少组
int T;//多少个点 
int x[10]={0};
int y[10]={0};
cin>>n;
while(n--){
cin>>T;
for(int j=0;j<T;j++)
{
cin>>x[j]>>y[j];
}
sort(x,x+T);
sort(y,y+T);

int xa=x[T/2];
int ya=y[T/2];
int sum=0;
for(int j=0;j<T;j++)
{
sum+=abs(x[j]-xa)+abs(y[j]-ya);
}
cout<<sum<<endl;
}
return 0;
}