题解 | #航海#_牛客博客

题目描述
二维平面的海上有n只船，每只船所在位置为(Xi,Yi)，每只船还有一个权值Wi，现在他们需要聚在一起商讨捕鱼大业，他们想请你找到一个点使得该点到其他点的带权曼哈顿距离之和最小。带权曼哈顿距离=实际曼哈顿距离∗权值。
输出表示最小的带权输出最小的带权距离之和。

方法一：暴力解法

求解思路
对于求解本题要寻找一个点使得该点到其他点的带权曼哈顿距离之和最小，我们自然想到遍历所有点，对于每一个点求一个带权曼哈顿距离，然后找出最小值即可。

图片说明

解题代码

class Solution {
public:
    struct node
    {
        int x, y, w;
        long long sumx, sumy; // 记录到其他点的 x 与 y 的曼哈顿距离
    };
    static bool cmp1(node& a, node& b)
    {
        return a.x < b.x; // 定义比较函数在x维度
    }
    static bool cmp2(node& a, node& b)
    {
        return a.y < b.y; // 定义比较函数在y维度
    }
    long long MinimumDistance(int n, vector<int>& x, vector<int>& y, vector<int>& w)
    {
        vector<node> boats(n); // 将每艘船的信息放在一起
        for(int i = 0; i < n; i++)
        {
            boats[i].x = x[i]; // 进行记录
            boats[i].y = y[i];
            boats[i].w = w[i];
        }
        sort(boats.begin(), boats.end(), cmp1); // 按照x排序
        long long sum1 = 0, sum2 = 0;
        long long sumw1 = 0, sumw2 = 0;
        for(int i = 0; i < n; i++)
        {   //算x维度的曼哈顿距离
            boats[i].sumx += boats[i].x * sumw1 - sum1;
            boats[n - i - 1].sumx += sum2 - boats[n - i - 1].x * sumw2;
            sumw1 += boats[i].w;
            sum1 += boats[i].w * boats[i].x;
            sumw2 += boats[n - i - 1].w;
            sum2 += boats[n - i - 1].x * boats[n - i - 1].w;
        }
        sort(boats.begin(), boats.end(), cmp2); // 按照y排序
        sum1 = 0, sumw1 = 0;
        sum2 = 0, sumw2 = 0;
        for(int i = 0; i < n; i++)
        {   //算y维度的曼哈顿距离
            boats[i].sumy += boats[i].y * sumw1 - sum1;
            boats[n - i - 1].sumy += sum2 - boats[n - i - 1].y * sumw2;
            sumw1 += boats[i].w;
            sum1 += boats[i].w * boats[i].y;
            sumw2 += boats[n - i - 1].w;
            sum2 += boats[n - i - 1].y * boats[n - i - 1].w;
        }
        long long min1 = LONG_LONG_MAX, min2 = LONG_LONG_MAX;
        for(int i = 0; i < n; i++) // 对每个点进行遍历，然后记录最小值
        {   //分别求x与y
            min1 = min(min1, boats[i].sumx);
            min2 = min(min2, boats[i].sumy);
        }
        return min1 + min2; // 返回结果即可
    }
};

复杂度分析
时间复杂度：使用快排，因此时间复杂度为 $O(NlogN)$
空间复杂度：使用辅助数组boats[n]，因此空间复杂度为 $O(N)$ ,N为boats数组的大小。

方法二：优化解法

求解思路
基于方法一，我们在对x方向或者y方向进行一维运算时，我们可以将其看成作一维的曼哈顿距离。并且我们可以想到使用二分法来对本题目进行优化。我们假设一个位置pos，其左侧有m个点，右侧有n-m个点，我们计算pos到其他点的距离，然后根据此数值来对接下来的新位置的距离进行计算。

图片说明

解题代码

class Solution {
public:
    long long Manhattandistance(int n, vector<int>& m, vector<int>& w, int max_value)
    {
        long long sum = 0, temp = 0, distance = 0; // 声明变量
        int median; // 中间位置
        vector<long long> nums_weight(max_value + 1, 0);
        for(int i = 0; i < n; i++)
        {
            nums_weight[m[i]] += w[i];
            sum += w[i]; // 进行曼哈顿距离求和计算
        }
        for(int i = 0; i <= max_value; i++)
        {
            temp += nums_weight[i];
            if(temp >=  sum / 2)
            {
                median = i; // 记录中间值
                break;
            }
        }
        for(int i = 0; i < n; i++)
            distance += abs(m[i] - median) * w[i];
        return distance; // f返回距离值
    }
    long long MinimumDistance(int n, vector<int>& x, vector<int>& y, vector<int>& w)
    {
        int max_x = 0, max_y = 0;
        for(int i = 0; i < n; i++)
        {   //分别找到 x y 最大值
            max_x = max(max_x, x[i]);
            max_y = max(max_y, y[i]);
        }
        return Manhattandistance(n, x, w, max_x) + Manhattandistance(n, y, w, max_y); // 计算x+y并返回结果
    }
};

复杂度分析
时间复杂度：一层循环，因此时间复杂度为 $O(N)$
空间复杂度：没有使用额外的内存地址空间，因此空间复杂度为 $O(1)$