A27614. 办事处选址编程实现: 现将某区域的地图变成一个平面的方格图，平面上有n处居⺠住宅，已知n处居⺠住宅，每处居 ⺠住宅位置所处的行数和列数，现计划设置一处便⺠办事处，使办事处去到各个住宅位置的距离 之和最短(只能上下左右走，且办事处可以和住宅处在同一个方格)，请问最短距离之和是多 少?例如:共有两处居⺠住宅，位置如下图:第一处居⺠住宅在0行0列，第二处居⺠住宅在0行1列，那么办事处可设置在0行0列 …
填空题
中等
知识点
题目描述
办事处选址
编程实现: 现将某区域的地图变成一个平面的方格图，平面上有n处居⺠住宅，已知n处居⺠住宅，每处居 ⺠住宅位置所处的行数和列数，现计划设置一处便⺠办事处，使办事处去到各个住宅位置的距离 之和最短(只能上下左右走，且办事处可以和住宅处在同一个方格)，请问最短距离之和是多 少?
例如:共有两处居⺠住宅，位置如下图:
第一处居⺠住宅在0行0列，第二处居⺠住宅在0行1列，那么办事处可设置在0行0列 处，到第一处居⺠住宅的距离为0，到第二处居⺠住宅的距离为1，最短距离之和为1。
输入描述
第一行输入一个正整数n，表示有n处居⺠住宅(1≤n≤10000)。 第二行往后n行，每一行输入一对数字，表示每处居⺠住宅的行数和列数(0≤行数<100，0≤列 数<100)，中间用空格隔开。
输出描述
输出最短距离之和。
输入样例
2
00
01
输出样例
1
参考答案
n = int(input())
lsx = []
lsy = []
fori inrange(0, n):
x, y = [int(i) fori ininput().split()]
lsx.append(x)
lsy.append(y)
lsx.sort()
lsy.sort()
midx = lsx[n//2]
midy = lsy[n//2]
tot = 0
fori inrange(0, n):
tot += abs(midx - lsx[i]) + abs(midy - lsy[i])
print(tot)
上一题
下一题