邮局选址
邮局选址
问题描述
在一个以XY轴表达的城市里， 个居民点散乱分布，居民点位置可以用坐标
表示。任意两点
和
间距离可以用
度量（曼哈顿距离）。居民希望在城市中选择建立邮局的最佳位置，使得
个居民点到邮局的距离总和最小。
贪心策略
这个问题可以将横纵坐标分开考虑，对答案没影响。问题可以转换为在一维坐标轴上选择一个点，使得所有点到它的距离和最小。
贪心策略：选择居民点的中位数位置建立邮局可以使总距离最小。
原因：
- 假设有两个点
、
，需要放置点
- 如果
放在
之间，距离和为
- 如果
- 所以最优解一定在中位数位置
算法实现
int solve(vector<int>& points) {
int n = points.size();
// 排序
sort(points.begin(), points.end());
// 选择中位数位置
int pos = points[n / 2];
// 计算总距离
int total = 0;
for (int p : points) {
total += abs(p - pos);
}
return total;
}
int minTotalDistance(vector<vector<int>>& points) {
int n = points.size();
if (n == 0) return 0;
vector<int> x(n), y(n);
for (int i = 0; i < n; i++) {
x[i] = points[i][0];
y[i] = points[i][1];
}
// 分别计算x和y方向的最小距离和
return solve(x) + solve(y);
}
class Solution {
private int solve(int[] points) {
Arrays.sort(points);
int pos = points[points.length / 2];
int total = 0;
for (int p : points) {
total += Math.abs(p - pos);
}
return total;
}
public int minTotalDistance(int[][] points) {
int n = points.length;
if (n == 0) return 0;
int[] x = new int[n];
int[] y = new int[n];
for (int i = 0; i < n; i++) {
x[i] = points[i][0];
y[i] = points[i][1];
}
return solve(x) + solve(y);
}
}
class Solution:
def solve(self, points: List[int]) -> int:
points.sort()
pos = points[len(points) // 2]
return sum(abs(p - pos) for p in points)
def minTotalDistance(self, points: List[List[int]]) -> int:
if not points:
return 0
x = [p[0] for p in points]
y = [p[1] for p in points]
return self.solve(x) + self.solve(y)
时间复杂度分析
- 排序：
- 计算距离和：
- 总时间复杂度：
- 空间复杂度：
正确性证明
-
一维情况下，中位数位置是最优解：
- 设邮局位置为
，居民点位置为
- 总距离
- 当
取得最小值
- 设邮局位置为
-
二维情况可以拆分为两个独立的一维问题：
坐标互不影响
- 分别取中位数
即可得到最优解
应用场景
- 物流中心选址
- 公共设施布局
- 网络服务器部署
- 移动基站布置
- 商业网点规划
注意事项
- 处理空输入
- 注意整数溢出
- 中位数的选择（当
为偶数时取任一中位数）
- 坐标范围的限制
- 距离计算的正确性
牛客代码笔记-牛栋 文章被收录于专栏
汗牛充栋，学海无涯。<br/> 内含算法知识点讲解，以及牛客题库精选例题。<br/> 学习算法，从牛栋开始。
深信服公司福利 493人发布
查看11道真题和解析
