Giả sử chúng ta có n điểm khác nhau trong không gian K chiều, giá trị n trong khoảng (2, 105), và giá trị k trong khoảng (1 đến 5). Chúng ta phải xác định điểm sao cho tổng khoảng cách Manhattan từ điểm kết quả đến n điểm được tối thiểu hóa.
Khoảng cách Manhattan giữa hai điểm P1(x1, y1) và P2(x2, y2), là |x1 – x2| + |y1 – y2|. Giả sử chiều là 3, và có ba điểm như (1, 1, 1), (2, 2, 2), (3, 3, 3), thì kết quả sẽ là (2, 2, 2).
Để giải quyết bài toán này, chúng ta phải sắp xếp các điểm theo tất cả K chiều và lấy kết quả từ các phần tử giữa của mỗi trong K chiều.
Ví dụ
#include<iostream> #include<vector> #include<cmath> #include<algorithm> using namespace std; void minimizeHanhattan(int n, int k, vector<vector<int> >& pointList) { for (int i = 0; i < k; ++i) //sort in all k dimension sort(pointList[i].begin(), pointList[i].end()); for (int i = 0; i < k; ++i) cout << pointList[i][(ceil((double)n / 2) - 1)] << " "; } int main() { int n = 4, k = 4; vector<vector<int> > point = { { 1, 5, 2, 4 }, { 6, 2, 0, 6 }, { 9, 5, 1, 3 }, { 6, 7, 5, 9 } }; minimizeHanhattan(n, k, point); }
Kết quả
2 2 3 6