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

题意整理

二维海面上有n只船，每只船有一个坐标，以及一个权值。
求最小的带权曼哈顿距离。

方法一（求极值）

1.解题思路

简要分析：
首先考虑一个简化版的情况，一维横轴上有n个点，要从这个n个点中，找到一个点，使得其他点移动到这个点的距离之和最小。假设当前处于第x个点的位置（位置p），当前的最小移动距离是dist，如果把这个点向右移动一位（移到p'），则最小移动距离dist变为 $dist'=dist+x-(n-x)$ （位于p左边的所有点到p的距离加一，总共加x，位于p右边的所有点到p的距离减一，总共减 $n-x$ ）。如果dist是一个关于x的函数，那么dist关于x的一阶导等于 $2*x-n$ ，于是x小于 $n/2$ 时，dist递减，x大于 $n/2$ 时，dist递增，dist在x等于 $n/2$ 时取得极小值，由于整个区间只有一个极小值，所以在 $n/2$ 处dist最小。

当n为奇数时， $n/2$ 向下取整，此时要比较 $n/2$ 处与 $n/2+1$ 处dist的大小，显然在 $n/2+1$ 处，dist最小；当n为偶数时，dist在 $n/2$ 与 $n/2+1$ 处的值相等。所以 $[1,n]$ 区间内最小值一定在 $n/2+1$ 处取得。

扩展分析：
明确了上述场景如何求最小距离后，再扩展到本题的情况。第一个扩展条件，本题是带有权值的，只需要将对应的坐标点的个数由1个变为权值数目。第二个扩展条件，本题是二维的，由于是曼哈顿距离，只需要分别计算x轴、y轴的情况，然后相加即可。

基本步骤：

初始化点对象集合、权值累加和。
将点对象集合按x轴坐标进行排序，寻找x轴上的极小值点对应坐标，根据这个坐标计算其他点到这个点的x轴上的曼哈顿距离。同样的方式，计算y轴上的曼哈顿距离，然后将x轴、y轴的曼哈顿距离相加即可得到所求最小距离。

动图展示：
图片说明

2.代码实现

import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 n
     * @param x int整型一维数组 x
     * @param y int整型一维数组 y
     * @param w int整型一维数组 w
     * @return long长整型
     */
    public long MinimumDistance (int n, int[] x, int[] y, int[] w) {
        //初始化点对象集合
        int[][] point=new int[n][3];
        //初始化权值累加和
        long wSum=0;
        for(int i=0;i<n;i++){
            point[i][0]=x[i];
            point[i][1]=y[i];
            point[i][2]=w[i];
            wSum+=w[i];
        }

        //初始化曼哈顿距离
        long sum_x=0,sum_y=0;

        //按横坐标进行排序
        Arrays.sort(point,(o1,o2)->o1[0]-o2[0]);

        //寻找x轴的极小值坐标
        long p_x=0;
        int x_median=0;
        for(int i=0;i<n;i++){
            p_x+=point[i][2];
            //如果恰好大于权值累加和一半，即找到对应坐标
            if(p_x>wSum/2){
                x_median=i;
                break;
            }
        }

        //计算x轴曼哈顿距离
        for(int i=0;i<n;i++){
            sum_x+=point[i][2]*Math.abs(point[i][0]-point[x_median][0]);
        }

        //按纵坐标进行排序
        Arrays.sort(point,(o1,o2)->o1[1]-o2[1]);

        //寻找y轴的极小值坐标
        long p_y=0;
        int y_median=0;
        for(int i=0;i<n;i++){
            p_y+=point[i][2];
            //如果恰好大于权值累加和一半，即找到对应坐标
            if(p_y>wSum/2){
                y_median=i;
                break;
            }
        }

        //计算y轴曼哈顿距离
        for(int i=0;i<n;i++){
            sum_y+=point[i][2]*Math.abs(point[i][1]-point[y_median][1]);
        }

        return sum_x+sum_y;
    }
}

3.复杂度分析

时间复杂度：排序的时间复杂度是 $O(n*log_2n)$ ，计算极值点坐标、求曼哈顿距离都是线性的时间复杂度，所以最终的时间复杂度是 $O(n*log_2n)$ 。
空间复杂度：需要额外大小为 $3*n$ 的point数组，所以空间复杂度是 $O(n)$ 。

方法二（枚举）

1.解题思路

假定已经按照x轴排好了三个点（从左到右分别是A，B，C），那么位于C左边的点到C的距离之和是 $A.w(C.x-A.x)+B.w(C.x-B.x)$ ，合并 $C.x$ 这个项可得 $(A.w+B.w)*C.x-(A.w*A.x+B.w*B.x)$ ，可以看出除了 $C.x$ 由固定某个点决定， $A.w+B.w$ 和 $A.w*A.x+B.w*B.x$ 都是逐项累加的，所以可以用两个变量记录这两个累加项。一轮循环完成之后，只是计算了所有左边的点到当前点的曼哈顿距离，还需考虑右边的点到当前点的曼哈顿距离。还是以C为例，（假设从左到右依次是C，D，E），位于C右边的点到C的距离之和是 $D.w(D.x-C.x)+E.w(E.x-C.x)$ ，合并 $C.x$ 可得 $(D.w*D.x+E.w*E.x)-(D.w+E.w)*C.x$ ，同样可以通过两个变量记录 $D.w+E.w$ 和 $D.w*D.x+E.w*E.x$ ，不过要倒序进行循环。

初始化点对象集合、x轴和y轴曼哈顿距离。
将点对象集合按x轴坐标进行排序，寻找x轴下每一个点的曼哈顿距离，记录在dist数组，然后同样的方式按y轴排序，计算y轴下每一个点的曼哈顿距离。
最后遍历所有的点，寻找x轴下最小的曼哈顿距离和y轴下最小的曼哈顿距离，将两者相加。

2.代码实现

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 n
     * @param x int整型一维数组 x
     * @param y int整型一维数组 y
     * @param w int整型一维数组 w
     * @return long长整型
     */
    public long MinimumDistance (int n, int[] x, int[] y, int[] w) {
        //初始化点对象集合
        int[][] point=new int[n][3];
        for(int i=0;i<n;i++){
            point[i][0]=x[i];
            point[i][1]=y[i];
            point[i][2]=w[i];
        }

        //初始化曼哈顿距离
        long[][] dist=new long[n][2];

        //按横坐标进行排序
        Arrays.sort(point,(o1,o2)->o1[0]-o2[0]);

        //求当前点前面的所有点到它的曼哈顿距离
        long pre_x_wSum=0,pre_x_mSum=0;
        for(int i=0;i<n;i++){
            dist[i][0]+=point[i][0]*pre_x_wSum-pre_x_mSum;
            pre_x_wSum+=point[i][2];
            pre_x_mSum+=point[i][0]*point[i][2];
        }

        //求当前点后面的所有点到它的曼哈顿距离
        long post_x_wSum=0,post_x_mSum=0;
        for(int i=n-1;i>=0;i--){
            dist[i][0]+=post_x_mSum-point[i][0]*post_x_wSum;
            post_x_wSum+=point[i][2];
            post_x_mSum+=point[i][0]*point[i][2];
        }

        //按纵坐标进行排序
        Arrays.sort(point,(o1,o2)->o1[1]-o2[1]);

        //求当前点前面的所有点到它的曼哈顿距离
        long pre_y_wSum=0,pre_y_mSum=0;
        for(int i=0;i<n;i++){
            dist[i][1]+=point[i][1]*pre_y_wSum-pre_y_mSum;
            pre_y_wSum+=point[i][2];
            pre_y_mSum+=point[i][1]*point[i][2];
        }

        //求当前点后面的所有点到它的曼哈顿距离
        long post_y_wSum=0,post_y_mSum=0;
        for(int i=n-1;i>=0;i--){
            dist[i][1]+=post_y_mSum-point[i][1]*post_y_wSum;
            post_y_wSum+=point[i][2];
            post_y_mSum+=point[i][1]*point[i][2];
        }

        //计算x轴曼哈顿距离和y轴曼哈顿距离，取两者之和
        long sum_x=Long.MAX_VALUE,sum_y=Long.MAX_VALUE;
        for(int i=0;i<n;i++){
            sum_x=Math.min(sum_x,dist[i][0]);
            sum_y=Math.min(sum_y,dist[i][1]);
        }
        return sum_x+sum_y;
    }
}

3.复杂度分析

时间复杂度：排序的时间复杂度是 $O(n*log_2n)$ ，计算x轴和y轴的曼哈顿距离都是线性的时间复杂度，所以最终的时间复杂度是 $O(n*log_2n)$ 。
空间复杂度：需要额外大小为 $3*n$ 的point数组，与方法一相比，多了dist数组的空间开销，空间复杂度是 $O(n)$ 。