鸿 网 互 联 www.68idc.cn

当前位置 : 服务器租用 > 编程语言开发 > erlang > >

51NOD 1108 距离之和最小 V2(中位数 + 化整为分)

来源:互联网 作者:佚名 时间:2016-07-17 21:13
传送门 三维空间上有N个点, 求一个点使它到这N个点的曼哈顿距离之和最小,输出这个最小的距离之和。 点(x1,y1,z1)到(x2,y2,z2)的曼哈顿距离就是|x1-x2| + |y1-y2| + |z1-z2|。即3维坐标差的绝对值之和。 Input 第1行:点的数量N。(2 = N = 10000) 第2 - N +

传送门
三维空间上有N个点, 求一个点使它到这N个点的曼哈顿距离之和最小,输出这个最小的距离之和。
点(x1,y1,z1)到(x2,y2,z2)的曼哈顿距离就是|x1-x2| + |y1-y2| + |z1-z2|。即3维坐标差的绝对值之和。
Input
第1行:点的数量N。(2 <= N <= 10000)
第2 - N + 1行:每行3个整数,中间用空格分隔,表示点的位置。(-10^9 <= X[i], Y[i], Z[i] <= 10^9)
Output
输出最小曼哈顿距离之和。
Input示例
4
1 1 1
-1 -1 -1
2 2 2
-2 -2 -2
Output示例
18

解题思路:
这个题目我们可以这么想,因为这是一个三维的坐标,所以我们整体想的话肯定不太好想,那么我们将这个题分解开来,因为曼哈顿距离就是|x1-x2| + |y1-y2| + |z1-z2|,所以我们我们可以分别求一下 x 坐标的最小值,y坐标的最小值,z坐标的最小值,那么最后的结果肯定就是这三个最小值相加,其实这也是体现了化整为分的想法,如果是单一坐标轴的话,这个问题就简单了,就是求一个中位数,排序一下取中介啊那个就行了。
My Code:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cstdlib>
#include <cmath>
using namespace std;
const int MAXN = 1e4+5;
typedef long long LL;
double x[MAXN],y[MAXN],z[MAXN];
int main()
{
    int n;
    while(~scanf("%d",&n))
    {
        for(int i=0; i<n; i++)
            scanf("%lf%lf%lf",&x[i],&y[i],&z[i]);
        double sum1 = 0, sum2 = 0, sum3 = 0;
        sort(x, x+n);
        double xx = x[n/2];
        sort(y, y+n);
        double yy = y[n/2];
        sort(z, z+n);
        double zz = z[n/2];
        for(int i=0; i<n; i++)
            sum1 += fabs(x[i]-xx);
        for(int i=0; i<n; i++)
            sum2 += fabs(y[i]-yy);
        for(int i=0; i<n; i++)
            sum3 += fabs(z[i]-zz);
        printf("%.0lf\n",sum1 + sum2 + sum3);
    }
    return 0;
}
网友评论
<