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