สมมติว่าเรามีจุดต่างกัน n จุดในพื้นที่มิติ K ค่าของ n อยู่ในช่วง (2, 105) และค่าของ k ในช่วง (1 ถึง 5) เราต้องกำหนดจุดที่จะลดผลรวมของระยะทางแมนฮัตตันจากจุดผลลัพธ์ไปยัง n จุด
ระยะทางแมนฮัตตันระหว่างจุด P1(x1, y1) และ P2(x2, y2) คือ |x1 – x2| + |y1 – y2|. สมมติว่ามิติเป็น 3 และมีสามจุดเช่น (1, 1, 1), (2, 2, 2), (3, 3, 3) จากนั้นผลลัพธ์จะเป็น (2, 2, 2)
ในการแก้ปัญหานี้ เราต้องจัดเรียงจุดในมิติ K ทั้งหมด และรับผลลัพธ์จากองค์ประกอบตรงกลางของแต่ละมิติ k
ตัวอย่าง
#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);
} ผลลัพธ์
2 2 3 6
