找到一个点，以使C ++中的曼哈顿距离之和最小
假设我们在K维空间中有n个不同的点，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
热门推荐
3 祝福语简短的微信
10 幼儿祝福语大全简短贺卡
11 感谢教官文案祝福语简短
12 鼠年同事祝福语简短创意
13 元旦祝福语 简短独特群发
14 妈咪跟我生日祝福语简短
15 给儿子新婚祝福语简短
16 伴娘祝福语长文案简短
17 恭喜高考完祝福语简短
18 生日祝福语送老公简短