街区最短路径问题
时间限制： 3000 ms | 内存限制： 65535 KB
难度： 4
- 描述
- 一个街区有很多住户，街区的街道只能为东西、南北两种方向。 住户只可以沿着街道行走。 各个街道之间的间隔相等。 用(x,y)来表示住户坐在的街区。 例如（4,20），表示用户在东西方向第4个街道，南北方向第20个街道。 现在要建一个邮局，使得各个住户到邮局的距离之和最少。 求现在这个邮局应该建在那个地方使得所有住户距离之和最小；
- 输入
- 第一行一个整数n<20，表示有n组测试数据，下面是n组数据; 每组第一行一个整数m<20,表示本组有m个住户，下面的m行每行有两个整数0<x,y<100，表示某个用户所在街区的坐标。 m行后是新一组的数据； 输出
- 每组数据输出到邮局最小的距离和，回车结束； 样例输入
-
231 12 11 252 9 5 2011 91 11 20
样例输出 -
244
来源 - 解题思路： 这个题就是一个策略问题，我把所有 x 坐标和 y 坐标分开，这样问题就变成了，给你 m 个数， 求这些数每个减去一个 x 的绝对值之和的最小值，min（∑|ai-x|)。 转化为： 给你 n 个数 a[1]、a[2]、……、a[n]; 求 min（∑|a[i]-x|) 首先 把这 n 数进行排序 ans = ∑ (a[n-i]-a[i]) 1<=i<=n/2; 其实就是在一个坐标轴上有 n 个点 求一个点到所以点的最短距离和 ，由于任意两点 x1 、x2，要使的距离和最小 则 x 必须在 x1 x2 之间 就行了，所以 n 个顶点排完序后 只要把 x 放在这 n 个数之间就行了
-
1 #include
2 #include 3 #include 4 5 using namespace std; 6 7 int main() 8 { 9 int T, m, sum;10 int x[20], y[20];11 scanf("%d", &T);12 while(T--)13 {14 scanf("%d", &m);15 for(int i = 0; i < m; ++i)16 scanf("%d%d", &x[i], &y[i]);17 sort(x, x+m);18 sort(y, y+m);19 sum = 0;20 for(int i = 0; i < m>>1; ++i)21 sum += x[m-i-1] - x[i] + y[m-1-i] - y[i];22 printf("%d\n", sum);23 }24 return 0;25 }