街区最短路径问题(曼哈顿距离)

zz/2024/2/25 22:11:10

街区最短路径问题


一个街区有很多住户,街区的街道只能为东西、南北两种方向。
住户只可以沿着街道行走。
各个街道之间的间隔相等。
用(x,y)来表示住户坐在的街区。
例如(4,20),表示用户在东西方向第4个街道,南北方向第20个街道。
现在要建一个邮局,使得各个住户到邮局的距离之和最少。
求现在这个邮局应该建在那个地方使得所有住户距离之和最小;


输入
第一行一个整数n<20,表示有n组测试数据,下面是n组数据;
每组第一行一个整数m<20,表示本组有m个住户,下面的m行每行有两个整数 0<x,y<100 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


曼哈顿距离:两点在南北方向上的距离加上在东西方向上的距离,即d(i,j)=|xi-xj|+|yi-yj|。对于一个具有正南正北、正东正西方向规则布局的城镇街道,从一点到达另一点的距离正是在南北方向上旅行的距离加上在东西方向上旅行的距离。
思路:因为只能东西和南北方向走,所以先把南北(X)和东西(Y)方向的坐标分开,分别求它们的最值,然后相加即可。分析可以得知,邮局的所建点必须在居民点上,要不然所得的值总会比最小值多出一部分来。知道这个然后让我们来分析:假设在坐标轴X上有n个点,是从1到n,我们所求的目标点在x上,先求点1和n到x的距离只和,很显然x点在1到n之间,然后再求2和n-1到x的距离之和,很显然x点在2和n-1之间,如此重复下去,x的范围不断减小,最后成为中位点。


#include<stdio.h>
#include<algorithm>
#include<string.h>
using namespace std;
int a[25],b[25];
int main(){int n,m;scanf("%d",&n);while(n--){memset(a,0,sizeof(a));memset(b,0,sizeof(b));scanf("%d",&m);for(int i=0;i<m;i++){scanf("%d%d",&a[i],&b[i]);}sort(a,a+m);sort(b,b+m);int sum;sum=0;for(int i=0;i<m/2;i++){sum+=a[m-i-1]-a[i]+b[m-i-1]-b[i];}printf("%d\n",sum);}return 0;
}

http://www.ngui.cc/zz/2641760.html

相关文章

HDU 找单词

Problem Description 假设有x1个字母A&#xff0c; x2个字母B,… x26个字母Z&#xff0c;同时假设字母A的价值为1&#xff0c;字母B的价值为2,… 字母Z的价值为26。那么&#xff0c;对于给定的字母&#xff0c;可以找到多少价值<50的单词呢&#xff1f;单词的价值就是组成一…

先验概率、后验概率、极大似然估计

先验概率 先验概率&#xff08;prior probability&#xff09;是指根据以往经验和分析得到的概率。例如投硬币事件&#xff0c;我们在执行这个事件之前就已经了解其符合二项分布&#xff0c;然后直接根据二项分布分析出的概率被称作是先验概率。它往往作为"由因求果"…

Python 网页爬虫

import re #匹配的库 import requests headers {Cookie:UM_distinctid16828a999356ee-01dbffc4bd71a8-33504275-144000-16828a99936840; CNZZDATA12553571271573548009-1546867979-%7C1546921578,Host:m.网站名称.com,User-Agent:Mozilla/5.0 (Windows NT 10.0; WOW64) Apple…

将文件数据读入结构体

将文件数据读入结构体 #include <stdio.h> #include <string.h> #include <stdlib.h> struct infostu {char no[20]; //学号 char name[20]; char sex[4];int age;char major[20]; //专业班级 }; int main() {int i0,j;struct infostu student[5…

CNN——卷积、池化与误差反向传播

卷积神经网络&#xff08;CNN&#xff09; 组成&#xff1a;输入层、卷积层、激活函数、池化层、全连接层 卷积神经网络中重要概念就&#xff1a; 深度&#xff1a;深度大小就等于所用的filter的个数[卷积层]&#xff0c;也可以理解为提取的层数。 权值共享&#xff1a;给一张…

iOS H5交互 -MUI

最近公司要求以后的项目要用iOS原生框架和h5页面结合完成,发现网上这方面的资料好少(js交互的资料是挺多的&#xff0c;我的h5页面是用MUI完成的&#xff0c;这方面的资料真的好少) 把我最近的进度做个总结 去MUI官网下载SDK 点击这里查看官方文档&#xff0c;下载SDK 下图是SD…

Hibernate配置异常

Orders和OrderItem配置 错误如图&#xff1a; 找了很久&#xff0c;才发现是因为和数据库对应的字段不同。 实体类&#xff1a; orders OrderItem xxx.hbm.xml 由于数据库对应的字段不存在itemid&#xff0c;所以图片上蓝色这一段代码应不要 数据库表格&#xff1a;

ssh+filter+cookie实现自动登陆

在ssh中&#xff0c;filter的web.xml没有正确配置的话&#xff0c;就会出现空指针异常&#xff0c;因为他执行的时候没有去找bean。也就是说filter和spring没有结合起来 实现用户自动登陆就是把用户信息保存在cookie里&#xff0c;当用户第二次访问的时候无需登陆。 实现自动…

hql语句中使用占位符:xx 的时候,查询所有查询查不出来

在hql语中&#xff0c;我们可以使用&#xff1f;也可以使用占位符&#xff1a;xx&#xff0c; 其中&#xff1f;可以使用query.setParameter(0,"%%"); 但是占位符使用query.setParameter("xx","%%")&#xff1b;的时候查询不出来所有的记录&am…

计算时间,指定时间的多少个月后

/*计算时间日期 */ function DateAdd(interval,number,date) { switch(interval){ case "m" : { if(date.getMonth()number>12){ date.setMonth(date.getMonth()number-12); date.s…