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