สมมติว่าเรามี n จุดที่แตกต่างกันในพื้นที่ K มิติ (K-dimensional Space) ค่าของ n อยู่ในช่วง (2, 10^5) และค่าของ k อยู่ในช่วง (1 ถึง 5) เราต้องกำหนดจุดที่ทำให้ผลรวมของระยะทางแมนฮัตตัน (Manhattan Distance) จากจุดผลลัพธ์ไปยัง 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 ทั้งหมด และเอาผลลัพธ์จากสมาชิกกลาง (Median) ของแต่ละมิติ 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) // จัดเรียงในมิติ K ทั้งหมด
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
