C ++最佳集合点
假设有两个或两个以上的人，他们想见面并最小化总的旅行距离。我们有一个值为0或1的2D网格，其中每个1标记该组中某人的住所。距离是使用“曼哈顿距离”公式计算的，因此距离(p1,p2)=|p2.x-p1.x|+|p2.y-p1.y|。
所以，如果输入像
则输出为6，因为从矩阵中我们可以了解到三个人分别生活在(0,0)，(0,4)和(2,2)：(0,2)是理想的交汇点，因为总行程2+2+2=6最小。
为了解决这个问题，我们将遵循以下步骤-
定义一个函数get()，它将采用数组v，
对数组v排序
i：=0
j：=v的大小
ret：=0
当我<j时-
ret：=ret+v[j]-v[i]
（将i增加1）
（将j减1）
返回ret
从主要方法中执行以下操作-
定义一个数组行
定义一个数组col
对于初始化i：=0，当i<网格大小时，更新（将i增加1），执行-
如果grid[i，j]不为零，则-
在行末插入我
在列末插入j
对于初始化j：=0，当j<grid[0]的大小时，更新（将j增加1），执行-
返回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