数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
服装设计
法学C++最佳会议地点
假设有一组两人或多人想见面并最大限度地减少总出行距离。我们有一个值为0或1的二维网格，其中每个1表示该组中某人的家。距离使用曼哈顿距离公式计算，因此distance(p1, p2) = |p2.x - p1.x| + |p2.y - p1.y|。
因此，如果输入如下所示：
| 1 | 0 | 0 | 0 | 1 |
| 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 | 0 |
则输出将为6，因为从矩阵中我们可以看出，三个人住在(0,0)、(0,4)和(2,2)：点(0,2)是一个理想的见面点，因为2+2+2=6的总出行距离最小。
为了解决这个问题，我们将遵循以下步骤：
定义一个函数get()，它将接收一个数组v，
对数组v进行排序
i := 0
j := v的大小
ret := 0
当i < j时，执行：
ret := ret + v[j] - v[i]
(将i加1)
(将j减1)
返回ret
从主方法执行以下操作：
定义一个数组row
定义一个数组col
初始化i := 0，当i < 网格大小，更新(将i加1)，执行：
初始化j := 0，当j < grid[0]的大小，更新(将j加1)，执行：
如果grid[i, j]不为零，则：
将i插入到row的末尾
将j插入到col的末尾
返回get(row) + get(col)
示例
让我们看看下面的实现以更好地理解：
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int minTotalDistance(vector<vector<int>>& grid) {
vector<int> row;
vector<int> col;
for (int i = 0; i < grid.size(); i++) {
for (int j = 0; j < grid[0].size(); j++) {
if (grid[i][j]) {
row.push_back(i);
col.push_back(j);
}
}
}
return get(row) + get(col);
}
int get(vector <int> v){
sort(v.begin(), v.end());
int i = 0;
int j = v.size() - 1;
int ret = 0;
while (i < j) {
ret += v[j] - v[i];
i++;
j--;
}
return ret;
}
};
main(){
Solution ob;
vector<vector<int>> v = {{1,0,0,0,1},{0,0,0,0,0},{0,0,1,0,0}};
cout << (ob.minTotalDistance(v));
}输入
{{1,0,0,0,1},{0,0,0,0,0},{0,0,1,0,0}}输出
6
更新于：2020年7月21日
浏览量：197
广告