Điểm gặp gỡ tốt nhất trong C++

Nhóm 2+ người muốn gặp nhau tại điểm sao cho tổng khoảng cách di chuyển nhỏ nhất. Lưới 2D: 1 = nhà ai đó. Khoảng cách Manhattan: |x2-x1| + |y2-y1|.

Ví dụ:

3 người tại (0,0), (0,4), (2,2). Điểm gặp lý tưởng (0,2) với tổng khoảng cách 2+2+2=6.

Phương pháp giải

Tách thành 2 bài toán 1D độc lập cho hàng và cột. Thu thập tọa độ hàng và cột của tất cả người. Sắp xếp mỗi mảng. Tổng khoảng cách tối thiểu = sum(v[j] - v[i]) với i từ đầu, j từ cuối (cặp ngoài cùng).

Ví dụ chương trình

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int minTotalDistance(vector>& grid) {
        vector row, 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 v) {
        sort(v.begin(), v.end());
        int i = 0, j = v.size() - 1, ret = 0;
        while (i < j) { ret += v[j] - v[i]; i++; j--; }
        return ret;
    }
};

int main() {
    Solution ob;
    vector> v = {{1,0,0,0,1}, {0,0,0,0,0}, {0,0,1,0,0}};
    cout << ob.minTotalDistance(v);
    return 0;
}

Đầu vào

{{1,0,0,0,1},{0,0,0,0,0},{0,0,1,0,0}}

Đầu ra

6