NYOJ 7 街区最短路径问题
2024-10-03 00:03:15
街区最短路径问题
时间限制: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 - 来源
- 经典题目
- 上传者
- iphxer
-
解题思路:代码很简单,不过题目值得思考!假设邮局坐标为<X,Y>,那么距离和为 for(i = 0; i < m; i++) sum += abs(xi-X)+abs(yi-Y);
为使sum最小,可以分别考虑X和Y的位置。考虑X,将xi按小到大进行排序,那么我们如何安放X呢,使abs(xi-X)的和最小呢?当然,放在中间了,使其在任意两间房子的连线上。那么假设有两个房子,那么abs(x1-X)+abs(x2-X) = x2-x1;因为x1 < x2;同样求得y的和;再根据曼哈顿距离公式,求得得距离和可以保证最小。#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <vector>
#include <climits>
#include <algorithm>
#include <cmath>
#define LL long long
using namespace std;
int main(){
int kase,x[],y[],i,m,ans;
scanf("%d",&kase);
while(kase--){
scanf("%d",&m);
for(i = ; i < m; i++)
scanf("%d %d",x+i,y+i);
sort(x,x+m);
sort(y,y+m);
for(ans = i = ; i < m/; i++)
ans += x[m-i-]-x[i] + y[m-i-]-y[i];
printf("%d\n",ans);
}
return ;
}
最新文章
- [osx] android studio下修改avd的hosts文件
- OO之美
- 《JAVA学习笔记 (final关键字)》
- 设置In_Memery
- socketWriter.go
- css---遮罩层
- 使用Dubbo的SPI扩展机制实现自定义LoadBalance——方法二 不改源码添加META-INF/dubbo元数据
- 移动App专项测试
- 虚拟机下Linux安装jdk
- POJ 1390 Blocks(DP + 思维)题解
- js截取字符串方法整理slice(), substr(), substring(), split()
- apache伪静态配置(URL重写)
- 【洛谷】【动态规划/01背包】P2925 [USACO08DEC]干草出售Hay For Sale
- 最菜的小鸟(mkdir -pv)
- linux导出sql数据
- 一步一步开始FPGA逻辑设计 - 高速接口之PCIe(转)
- 制作centos sshd 镜像
- 5.翻译:EF基础系列---EF中的上下文类
- IplImage 与mat之间的转换及释放内存
- Condition使用
热门文章
- 极简的css浮动窗口
- MySQL57修改root密碼
- div 绝对定位
- leetcode134 Gas Station
- Java生成-zipf分布的数据集(自定义倾斜度,用作spark data skew测试)
- Django之CSRF问题
- C# 一维数组 冒泡排序
- iOS图片目录批量复制到android图片目录
- iOS,APP退到后台,获取推送成功的内容并且语音播报内容。
- DatePicker 注意点 1.不用v-model 用:value 2.配合on-change进行回调 3.初始值 当天的用 (new Date()).toLocaleDateString().replace(/\//g, &#39;-&#39;)