首页 > 试题广场 >

航海

[编程题]航海
  • 热度指数:628 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
二维平面的海上有只船,每只船所在位置为,每只船还有一个权值,现在他们需要聚在一起商讨捕鱼大业,他们想请你找到一个点使得该点到其他点的带权曼哈顿距离之和最小。带权曼哈顿距离=实际曼哈顿距离权值。

输出表示最小的带权输出最小的带权距离之和。

示例1

输入

2,[2,1],[1,1],[1,1]

输出

1

说明

可以选取(1,1)点,答案为1

备注:
数组下标从0开始

 

class Solution {
public:
    /**
     * 
     * @param n int整型 n
     * @param x int整型一维数组 x
     * @param xLen int x数组长度
     * @param y int整型一维数组 y
     * @param yLen int y数组长度
     * @param w int整型一维数组 w
     * @param wLen int w数组长度
     * @return long长整型
     */
    struct P{
        int x, y, w;
    };
    static bool cmpx(P p1, P p2){
        return p1.x < p2.x;
    }
    static bool cmpy(P p1, P p2){
        return p1.y < p2.y;
    }
    long long MinimumDistance(int n, int* x, int xLen, int* y, int yLen, int* w, int wLen) {
        long long Min = 0, W = 0, s=0;
        int xx=0, yy=0;
        P p[n];
        for(int i=0;i<n;i++){
            p[i].x = x[i];
            p[i].y = y[i];
            p[i].w = w[i];
            W += w[i];
        }
        W >>= 1;

        sort(p, p+n, cmpx);
        for(int i=0;i<n;i++){
            s += p[i].w;
            if(s > W){
                xx = i;
                break;
            }
        }
        for(auto &t: p)
            Min += abs(t.x - p[xx].x) * t.w;
        
        s = 0;
        sort(p, p+n, cmpy);
        for(int i=0;i<n;i++){
            s += p[i].w;
            if(s > W){
                yy = i;
                break;
            }
        }
        for(auto &t: p)
            Min += abs(t.y - p[yy].y) * t.w;

        return Min;
    }
};

发表于 2020-08-18 02:00:49 回复(0)