資料結構
網路
關係資料庫管理系統 (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
廣告