化妆品网站开发的背景,wordpress在线搭建,透明管理系统网站模板,网站怎么做黑链接题干#xff1a;
三维空间上有N个点, 求一个点使它到这N个点的曼哈顿距离之和最小#xff0c;输出这个最小的距离之和。
点(x1,y1,z1)到(x2,y2,z2)的曼哈顿距离就是|x1-x2| |y1-y2| |z1-z2|。即3维坐标差的绝对值之和。 收起
输入
第1行#xff1a;点的数量N。(2 …题干
三维空间上有N个点, 求一个点使它到这N个点的曼哈顿距离之和最小输出这个最小的距离之和。
点(x1,y1,z1)到(x2,y2,z2)的曼哈顿距离就是|x1-x2| |y1-y2| |z1-z2|。即3维坐标差的绝对值之和。 收起
输入
第1行点的数量N。(2 N 10000)
第2 - N 1行每行3个整数中间用空格分隔表示点的位置。-10^9 X[i], Y[i], Z[i] 10^9)
输出
输出最小曼哈顿距离之和。
输入样例
4
1 1 1
-1 -1 -1
2 2 2
-2 -2 -2
输出样例
18
解题报告 用中位数的性质将三个坐标拆开来求。注意这题不能直接取n/2了虽然一般情况下都是成立的但是如果n1那就GG了。所以保险起见以后用的时候还是奇数偶数分开讨论好了。
AC代码
#includecstdio
#includeiostream
#includealgorithm
#includequeue
#includemap
#includevector
#includeset
#includestring
#includecmath
#includecstring
#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;cinn;for(int i 1; in; i) {scanf(%lld%lld%lld,p[i].x,p[i].y,p[i].z);}sort(p1,pn1,cmp1);int fk n%2 1 ? n/21 : n/2; for(int i 1; in; i) {sum abs(p[i].x - p[fk].x);}sort(p1,pn1,cmp2);for(int i 1; in; i) {sum abs(p[i].y - p[fk].y);}sort(p1,pn1,cmp3);for(int i 1; in; i) {sum abs(p[i].z - p[fk].z);}cout sum;return 0 ;}
