NYOJ——街区最短路径问题
街区最短路径问题
时间限制： 3000 ms | 内存限制：65535 KB
难度： 4
描述
⼀个街区有很多住户，街区的街道只能为东西、南北两种⽅向。
住户只可以沿着街道⾏⾛。
各个街道之间的间隔相等。坐月子吃什么水果
⽤(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
最佳代码
#include<iostream>
#include<algorithm>
using namespace std;
int x[30],y[30],n,m,i;;
int main()
{
cin>>n;
while(n--)
{
cin>>m;
for(i=0;i<m;i++)
cin>>x[i]>>y[i];
sort(x,x+m);
sort(y,y+m);
最近比较火的歌
int sum=0;
入住英文
for(i=0;i<m/2;i++)
sum+=x[m-1-i]-x[i]+y[m-1-i]-y[i];
陈孝天
cout<<sum<<endl;
}
return0;
}
sort是c++的排序函数，默认是升序。感觉⽐qsort容易记住。
这个想法⾮常好，两点横坐标距离差就是要⾛到报刊亭的横向距离，纵向也⼀样。我写的是⽤穷举法，枚举每个位置，这种⽅法⽐较容易想，但很慢，还因为⼀个⼩错误提交了⼗⼏遍....细节是最重要的呀。
#include<stdio.h>
#define MAXN 1000000
int abs(int a)
{
return a>0? a:(-a);
}
int main()
{
int n;
scanf("%d",&n);
while(n--)
{
桔梗的作用和功效int m,i=0;
scanf("%d",&m);
int x[20],y[20];
for(i=0;i<m;i++)
{
scanf("%d%d",&x[i],&y[i]);
}
int j,maxx=x[0],maxy=y[0],minx=x[0],miny=y[0];
for(j=0;j<m;j++)
{
if(x[j]>maxx)
maxx=x[j];
if(y[j]>maxy)
maxy=y[j];
if(x[j]<minx)
minx=x[j];
if(y[j]<miny)
miny=y[j];
}
int mdis=MAXN,k;
for(i=minx;i<=maxx;i++)
爆炒香菇{
for(j=miny;j<=maxy;j++)
{
int sum=0;
for(k=0;k<m;k++)
{
sum+=abs(x[k]-i)+abs(y[k]-j);
}
if(sum<mdis)
我的科学梦作文mdis=sum;
}
}
printf("%d\n",mdis);
}
}
