題干：

三維空間上有N個點, 求一個點使它到這N個點的曼哈頓距離之和最小，輸出這個最小的距離之和。

點(x1,y1,z1)到(x2,y2,z2)的曼哈頓距離就是|x1-x2| + |y1-y2| + |z1-z2|。即3維坐標差的絕對值之和。

?收起

輸入

第1行：點的數(shù)量N。(2 <= N <= 10000) 第2 - N + 1行：每行3個整數(shù)，中間用空格分隔，表示點的位置。（-10^9 <= X[i], Y[i], Z[i] <= 10^9)

輸出

輸出最小曼哈頓距離之和。

輸入樣例

4 1 1 1 -1 -1 -1 2 2 2 -2 -2 -2

輸出樣例

18

解題報告：

? ?用中位數(shù)的性質(zhì)將三個坐標拆開來求。注意這題不能直接取n/2了，，，雖然一般情況下都是成立的，但是如果n=1那就GG了。所以保險起見以后用的時候還是奇數(shù)偶數(shù)分開討論好了。

AC代碼：

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define ll long long #define pb push_back #define pm make_pair using namespace std; const int MAX = 2e5 + 5; struct Node {ll x,y,z; } p[MAX]; bool cmp1(Node a,Node b) {return a.x < b.x; } bool cmp2(Node a,Node b) {return a.y < b.y; } bool cmp3(Node a,Node b) {return a.z < b.z; } int main() {int n;ll sum = 0;cin>>n;for(int i =1; i<=n; i++) {scanf("%lld%lld%lld",&p[i].x,&p[i].y,&p[i].z);}sort(p+1,p+n+1,cmp1);int fk = n%2 == 1 ? n/2+1 : n/2; for(int i = 1; i<=n; i++) {sum += abs(p[i].x - p[fk].x);}sort(p+1,p+n+1,cmp2);for(int i = 1; i<=n; i++) {sum += abs(p[i].y - p[fk].y);}sort(p+1,p+n+1,cmp3);for(int i = 1; i<=n; i++) {sum += abs(p[i].z - p[fk].z);}cout << sum;return 0 ;}

?

總結

以上是生活随笔為你收集整理的【51nod - 1108】距离之和最小 V2（曼哈顿距离，中位数性质）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。