异想天开

What's the true meaning of light, Could you tell me why

街区最短路径问题

日期:2015-05-19 09:38:26
  
最后更新日期:2015-05-19 09:39:00
http://acm.nyist.net/JudgeOnline/problem.php?pid=7
描述
一个街区有很多住户,街区的街道只能为东西、南北两种方向。

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

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

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

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

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

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

输入
第一行一个整数n<20,表示有n组测试数据,下面是n组数据;
每组第一行一个整数m<20,表示本组有m个住户,下面的m行每行有两个整数0m行后是新一组的数据;
输出
每组数据输出到邮局最小的距离和,回车结束;
样例输入
2
3
1 1
2 1
1 2
5
2 9
5 20
11 9
1 1
1 20
样例输出
2
44
解析:
这题开始没怎么看懂题目,忽略了街道只有南北和东西走向。南北方向和东西方向,可以分开考虑。坐标轴上的从小到大排列的n个点,A1,A2,A3...An。那么:
1.首先到所有点距离之和最小的点必须在A1到An之间。
2.距离A1和An点之和最小的点,在A1和An之间。
3.距离A2和A(n-1)点之和最小的点,在A2和A(n-1)之间。符合该条件,也符合条件1。
4.依次类推,不断缩小范围,最后就是中位点。
[code lang="cpp"]
#include<stdio.h>
#include<stdlib.h>
const int LEN=101;
struct node{
int x;
int y;
}data[LEN];

int cmp(const void *a , const void *b){
int *x=(int *)a;
int *y=(int *)b;
return *x>*y;
}

int solve_impl(int n)
{
int a[LEN];
int b[LEN];
for (int i=0; i<n; ++i){
a[i]=data[i].x;
b[i]=data[i].y;
}

qsort(a,n,sizeof(int),cmp);
qsort(b,n,sizeof(int),cmp);

int sum=0;
for (int i=0; i<n/2; ++i){
sum += a[n-i-1]-a[i] + b[n-i-1]-b[i];
}
printf("%d\n",sum);
return sum;
}

int solve(){
int t;
scanf("%d",&t);
while(t--){
int n;
scanf("%d",&n);
for (int i=0; i<n; ++i){
scanf("%d %d",&data[i].x,&data[i].y);
}
solve_impl(n);
}
return 0;
}

int main()
{
solve();
return 0;
}
[/code]