leetcode-zj-future03：快递中转站选址题目解题

93 阅读 0 评论 62 点赞

我是靠谱客的博主勤奋灯泡，这篇文章主要介绍leetcode-zj-future03：快递中转站选址题目解题，现在分享给大家，希望可以做个参考。

leetcode-zj-future03：快递中转站选址

题目
解题
- 方法一：

题目

题目连接
某区域地图记录在 k 二维数组 area，其中 0 表示空地，1 表示快递分发点。

若希望选取一个地点设立中转站，使得中转站至各快递分发点的「曼哈顿距离」总和最小。请返回这个最小的距离总和。

注意：

曼哈顿距离：distance(p1, p2) = |p2.x - p1.x| + |p2.y - p1.y|
所有位置均可作为快递中转站的设立点。

示例 1：
在这里插入图片描述

复制代码

1
2
3
4
5
输入: area = [[0,1,0,0,0],[0,0,0,0,1],[0,0,1,0,0]]
输出: 5 
解释: 三个快递分发点分别位于(0,1)，(1,4) 和 (2,2):
     (1,2) 是最佳的中转站选址，总距离为 2 + 2 + 1 = 5。

示例 2:

复制代码

1
2
3
4
输入: area = [[1,1],[1,1]]
输出: 4
解释: (0,0) 是最佳的中转站选址之一，总距离为 0 + 1 + 1 + 2 = 4。

在这里插入图片描述

解题

方法一：

由于是曼哈顿距离，其实可以可以化解二维为一维的问题
对于下图中，选取箭头所指的选为中转站，距离最短
在这里插入图片描述

在这里插入图片描述

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    int buildTransferStation(vector<vector<int>>& area) {
        vector<int> x;
        vector<int> y;
        for(int i=0;i<area.size();i++){
            for(int j=0;j<area[0].size();j++){
                if(area[i][j]==1){
                    x.push_back(i);
                    y.push_back(j);
                }
            }
        }
        sort(x.begin(),x.end());
        sort(y.begin(),y.end());
        int mid=x.size()/2;
        int res=0;
        for(int xi:x){
            res+=abs(xi-x[mid]);
        }
        for(int yi:y){
            res+=abs(yi-y[mid]);
        }
        return res;
    }
};