航海题解

首先来看一个简化版的问题，一条线上有个点，为了把所有点移到一起，怎么移动花费最小？
假设我们现在选取了一个位置，它左边及处有个点，右边有个点，现在总花费为。我们现在让右移一个单位，记为，那么很明显处的花费变成了，可以发现从左到右花费是先减少再增大的，不难得知这是一个单峰函数，且在的时候取得最值，其实这也是中位数的一个应用。那么解决这个简化版的问题就可以去找中位数来求解。
对于本题来说还有两个问题没解决。
首先是权值，其实权值可以看成有个点在这个位置，并且继续用上述得到的性质就好了。
最后还有一个问题就是本题是二维的。虽然本题是二维，但是细想可以发现，因为是曼哈顿距离，所以与是互不影响的，分别对求一次答案加起来就好了，注意要用 噢。
本题时间复杂度，空间复杂度。
中位数代码：

struct node {
    long long x,y,w;
}a[110000];
bool cmp1(node a,node b) {
    return a.x<b.x;
}
bool cmp2(node a,node b) {
    return a.y<b.y;
}
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长整型
     */
    long long MinimumDistance(int n, int* x, int xLen, int* y, int yLen, int* w, int wLen) {
        // write code here
        long long sum=0,ans=0;
        for(int i=1;i<=n;i++) {
            a[i].x=x[i-1];
            a[i].y=y[i-1];
            a[i].w=w[i-1];
            sum+=a[i].w;
        }
        sum>>=1;
        sort(a+1,a+1+n,cmp1);//按照x排序
        long long tmp=0,ch;
        for(int i=1;i<=n;i++) {//找中位数位置
            tmp+=a[i].w;
            if(tmp>sum) {
                ch=a[i].x;
                break;
            }
        }
        for(int i=1;i<=n;i++)
            ans+=abs(a[i].x-ch)*a[i].w;
        //y
        sort(a+1,a+1+n,cmp2);//按照y排序
        tmp=0;
        for(int i=1;i<=n;i++) {//找中位数位置
            tmp+=a[i].w;
            if(tmp>sum) {
                ch=a[i].y;
                break;
            }
        }
        for(int i=1;i<=n;i++)
            ans+=abs(a[i].y-ch)*a[i].w;
        return ans;
    }
};

除了中位数的做法呢咋们可以依次枚举计算贡献。
假定现在我们已经按x排好序了分别是ABC三个点，那么C到AB的距离和是
C.w|C.x-A.x|+B.w|C.x-B.x|，又因为已经排序了，那么绝对值可以去掉，
得：A.w(C.x-A.x)+B.w(C.x-B.x)
化简得：
A.wC.x-A.wA.x+B.wC.x-B.w*B.x
C.x(A.w+B.w)-(A.wA.x+B.w*B.x)
假设有四个点ABCD,计算D到ABC的距离
化简得：
D.x(A.w+B.w+C.w)-(A.wA.x+B.wB.x+C.wC.x)
在计算过程中跟踪(A.w+B.w+C.w)，代码中记做ww，
(A.wA.x+B.wB.x+C.wC.x)，代码中记做sum

class Solution {
public:
    struct node {
    long long x, y, w,sum1,sum2;
};
long long MinimumDistance(int n, int* x, int xLen, int* y, int yLen, int* w, int wLen) {
    // write code here
    typedef long long ll;
    vector<node>a(n);
    for (int i = 0; i < xLen; i++)
        a[i] = { x[i],y[i],w[i],0,0 };
    sort(a.begin(), a.end(), [](node& a, node& b) { return a.x < b.x; });
    ll sum=0,ww=0,sum1=0,ww1=0,ans=INT64_MAX;
    for (ll i = 0; i < n; i++) {
        a[i].sum1 += a[i].x*ww-sum;
        a[n-i-1].sum1 += sum1-a[n-i-1].x*ww1;
        sum += a[i].x*a[i].w;
        ww += a[i].w;
        sum1 += a[n-i-1].x*a[n-i-1].w;
        ww1 += a[n-i-1].w;
    }
    sort(a.begin(), a.end(), [](node& a, node& b) { return a.y < b.y; });
    sum=0,ww=0,sum1=0,ww1=0;
    for (int i = 0; i < n; i++) {
        a[i].sum2+=a[i].y*ww-sum;
        a[n-i-1].sum2+=sum1-a[n-i-1].y*ww1;
        sum+=a[i].y*a[i].w;
        ww+=a[i].w;
        sum1+=a[n-i-1].y*a[n-i-1].w;
        ww1+=a[n-i-1].w;
    }
    ll ch1=1e18,ch2=1e18;
    for(int i=0;i<n;i++) {
        ch1=min(ch1,a[i].sum1);
        ch2=min(ch2,a[i].sum2);
    }
    return ch1+ch2;
}
};