题解 | #航海#

算法思想一：暴力法

解题思路：

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

由题值：

A点到B、C两点之间的带权曼哈顿距离：

若单独计算x这一维的曼哈顿距离有：

依次推广可知依次累加

,

代码展示：

C++版本

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 n
     * @param x int整型vector x
     * @param y int整型vector y
     * @param w int整型vector w
     * @return long长整型
     */
    struct node
    {
        int x, y, w;
        long long sumx, sumy; // 记录到其他点的 x 与 y 的曼哈顿距离
    };
    static bool comp1(node& a, node& b)
    {
        return a.x < b.x; // 定义比较函数在x维度
    }
    static bool comp2(node& a, node& b)
    {
        return a.y < b.y; // 定义比较函数在y维度
    }
    long long MinimumDistance(int n, vector<int>& x, vector<int>& y, vector<int>& w) {
        // write code here
        vector 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(), comp1); //按照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(), comp2); //按照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; // 返回结果即可
    }
};

复杂度分析

时间复杂度：使用排序算法时间，遍历时间

空间复杂度：辅助数组占用空间

算法思想二：二分法

解题思路：

对于 x 方向或者 y 方向单独的一维进行运算时，就可以看成一维的曼哈顿距离计算。假设存在 n 个数，存在一个位置 pos， pos 左侧有 x 个点（包括 pos 位置），右侧 n-x 个点。
其他点到该点的带权曼哈顿距离为 res，将该点向右移动距离 z ，此时新位置上 pos' 其他点到该点的带权曼哈顿距离为 ，边界为 (向上取整)
图解：

代码展示：

C++版本

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 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;
    }
    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]);
        }
        //x+y
        return Manhattandistance(n, x, w, max_x) + Manhattandistance(n, y, w, max_y);
    }
};

复杂度分析

时间复杂度：都是单层遍历时间

空间复杂度：仅使用常数级空间变量