@TOCpython实现邮箱选址问题
在一个按照东西和南北方向划分成规整的星球里，
n个阿伟点散乱地分布在不同的星球中。
用x坐标表示东西向，用y坐标表示南北向。
各阿伟点的位置可以由 坐标(x,y)表示。 星球中任意2点(x1,y1)和(x2,y2)之间的距离可以用数值 ∣x1?x2∣+∣y1?y2∣度量。
阿伟们希望在星球中选择建立邮箱的最佳位置，使n个阿伟点到邮箱的距离总和最小。
输入格式:
第1行是阿伟点数n，1≤n≤10000。接下来n行是阿伟的位置，每行2个整数x和y，-10000≤x，y≤10000。
输出格式:
1个数，是n个阿伟点到邮箱的距离总和的最小值。
输入样例:
5
1 2
2 2
1 3
3 -2
3 3
输出样例:
10
前言
假期参加了学校的一个算法培训，遇到了一个蛮有意思的邮箱选址问题，就试着用python做了一下，不过最后效果肯定没有C/C++实现的效果那么好就对了（是从我这个小白的角度来看的哈，大佬们有其他更好的思路算法实现还请不吝赐教）
一、思路实现
1、键盘输入坐标点的个数以及相应的坐标，用python的列表数据结构进行存储；
2、通过循环将键盘输入的坐标点赋值给相应的坐标列表，横纵坐标各自存放一个列表；
3、采用快速排序的方法对各列表内横纵坐标排序（quick_sort自定义函数），并且定义fun()函数进行递归调用；
4、求出两个列表各自的中位数（因为这里题目求的是距离总和的最小值，对应的算法就是和中位数定理相关的）。我这里是引用python的numpy库median方法求出中位数；
5、题目已经给出了距离计算公式，因此自定义distinction（）函数进行计算并返回距离综合值；
二、使用步骤
1.引入库
代码如下：
import numpy as np
2.快速排序
代码如下：
# 快速排序功能
def quick_sort(list1, low, high):
# 列表里的第一个数据作为快速排序的关键字
key = list1[low]
while low < high:
while low < high and list1[high] >= key:
high -= 1
list1[low] = list1[high]
while low < high and list1[low] <= key:
low += 1
list1[high] = list1[low]
list1[low] = key
return low
此处快速排序选择列表第一个数据作为排序基准关键字
3.递归调用快速排序
代码如下：
# 递归调用
def fun(list1, low, high):
if low < high:
# 获取中轴位置
mid = quick_sort(list1, low, high)
# 子表划分（左)
quick_sort(list1, low, mid - 1)
# 右
quick_sort(list1, mid + 1, high)
4.求最佳点到各点距离综合
代码如下：
# 求各点距离最小
def distance(list_x, list_y, median_x, median_y):
count = 0
for i in range(len(list_x)):
count += abs(list_x[i]-median_x)+abs(list_y[i]-median_y)
print(int(count))
5.定义主函数
代码如下：
def main():
list_x = []
list_y = []
n = eval(input())
for i in range(n):
x, y = map(int, input().split())
list_x.append(x)
list_y.append(y)
fun(list_x, 0, n-1)
fun(list_y, 0, n-1)
# 求各列表的中位数
median_x = np.median(list_x)
median_y = np.median(list_y)
distance(list_x, list_y, median_x, median_y)
6.最后调用
代码如下：（这是我同学写的，找他讨要登上来了）
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
typedef pair<int, int> pr;
pr p[10000];
int fun(int i, int j,pr p[], int size) {
int min = 0;
for (int k = 0; k < size; k++) {
min += (fabs(p[k].first - i) + fabs(p[k].second - j));
}
return min;
}
int main() {
int num, x, y;
int minx, miny, maxx, maxy;
cin >> num;
for (int i = 0; i < num; i++) {
cin >> x >> y;
p[i].first = x;
p[i].second = y;
}
maxx = minx = p[0].first;
maxy = miny = p[0].second;
for (int i = 1; i < num; i++) {
if (p[i].first < minx)
minx = p[i].first;
if (p[i].first > maxx)
maxx = p[i].first;
if (p[i].second < miny)
miny = p[i].second;
if (p[i].second > maxy)
maxy = p[i].second;
}
int min = 100000;
for (int i = minx; i <= maxx; i++) {
for (int j = miny; j <= maxy; j++) {
int mm = fun(i, j, p, num);
if (mm < min) {
min = mm;
}
}
}
cout << min;
return 0;
}
7.C/C++版本实现
代码如下：
if __name__ == '__main__':
main()
8.二者版本的耗费资源对比
C/C++版本：
python版本：
这差距，说多了都是泪，大家看着就当消遣消遣吧
总结
其实在这个程序里有几个知识点对我来说是新学，边查边写的，在我的实现过程中起了很大的作用：
一个是map函数的使用，当时我是想说用两次for循环配合break来对横纵坐标轮流赋值一次的，但是血红的报错打消了我的想法，就CSDN了好久，从众多的二维列表方法里找到了map函数这个解决方法，这里附上这位前辈的原博客：转载博客
另一个则是关于排序算法的实现过程，也查阅了CSDN上另一位博主的总结博客，转载链接
最后，写这个代码的时候查了查同类回答，发现有要求各个点带有权值的问题进阶版，我这里题目没有要求有权值，所以有需求的读者们需要自行改进一下；
感谢你的阅读~