题解 | #航海#

思路：

题目的主要信息：

• 一共有n艘船，默认从其中选出一艘船的位置到其他所有船的带权曼哈顿距离最小。
• 带权曼哈顿距离公式：如果AB两点的坐标分别为，，权重分别是与，则从A到B的曼哈顿距离 = ，我们可以发现二者是分开算的，因此我们单独计算，然后相加。

方法一：暴力法
具体做法：
对于C点到AB两点的曼哈顿距离，我们有，如果我们对一维单独进行排序，单独计算x这一维的曼哈顿距离有：，容易用数学归纳法证明这个公式可以推广到一个点到任意多个点。因为我们可以在遍历的时候就依次累加，来完成公式。

class Solution {
public:
    struct node{
        int x, y, w;
        long long sumx, sumy; //记录到其他点的x 与 y的曼哈顿距离
    };
    static bool comp1(node& a, node& b){
        return a.x < b.x;
    }
    static bool comp2(node& a, node& b){
        return a.y < b.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(), 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;
    }
};

复杂度分析：

• 时间复杂度：，复杂度为sort函数的复杂度，多次遍历都是，较小，可以舍弃
• 空间复杂度：，辅助数组boats的大小

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

同理，该问题可以转为上下，求y方向的距离。

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;
    }
    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);
    }
};

复杂度分析：

• 时间复杂度：，都是单层遍历
• 空间复杂度：，根据函数中的辅助数组nums_weight，最坏空间取决于最大的坐标位置，因此调用了两次，因此谁更大最坏空间就是谁的最大值