https://www.hackerrank.com/contests/infinitum16-firsttimer/challenges/hyperspace-travel

給出n個點，是一個m維坐標，要求找一個點，使得這n個點到這個點的哈曼頓距離之和最小。輸出字母序最小的一組解

考慮一維的時候，是很簡單的，先把x排序，然后取中點就行，偶數的話取左邊那個即可。

然而這是n維，但是是一樣的，因為x和y是分開算的，什么意思呢？就是是固定的，對于一個點(x0,y0)去到(x1,y1)，固定的是要走x1-x0步（x方向） ?y是固定走y1-y0步的，

所以x和y不互相影響，把m維拆開來算即可

#include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <algorithm> using namespace std; #define inf (0x3f3f3f3f) typedef long long int LL;#include <iostream> #include <sstream> #include <vector> #include <set> #include <map> #include <queue> #include <string> const int maxn = 100 + 20; vector<int>pp[maxn]; void work() {int n, m;cin >> n >> m;for (int i = 1; i <= n; ++i) {for (int j = 1; j <= m; ++j) {int x;cin >> x;pp[j].push_back(x);}}for (int i = 1; i <= m; ++i) {sort(pp[i].begin(), pp[i].end());}int to = 104;if (n & 1) {for (int i = 1; i <= m; ++i) { // cout << pp[i][m / 2] << endl;pp[to].push_back(pp[i][n / 2]);}} else {for (int i = 1; i <= m; ++i) {pp[to].push_back(pp[i][n / 2 - 1]);}}for (int i = 0; i < m - 1; ++i) {cout << pp[to][i] << " ";}cout << pp[to][m - 1] << endl; }int main() { #ifdef localfreopen("data.txt","r",stdin); #endifwork();return 0; } View Code

?

轉載于:https://www.cnblogs.com/liuweimingcprogram/p/5873654.html

總結

以上是生活随笔為你收集整理的Hyperspace Travel的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。