集中问题题解

【前言】
一道简单题。
【暴力】
枚举坐标系上的点，统计答案即可。
【正解】
可以发现题目中距离是切比雪夫距离，这样计算距离和非常不方便。
我们知道切比雪夫距离和曼哈顿距离是可以相互转化的。
切比雪夫距离相同的点可以围成一个与坐标轴平行的正方形，而曼哈顿距离相同的点则可以围成一个与坐标轴成45°的正方形。
考虑曼哈顿距离的表达式：|x1−x2|+|y1−y2|，其实可以表示成：
max{x1−x2+y1−y2,x1−x2+y2−y1,x2−x1+y1−y2,x2−x1+y2−y1}(1)
考虑将两个点变化为(x1+y1,x1−y1),(x2+y2,x2−y2)
那么变化后两点的切比雪夫距离为max((|(x1+y1)−(x2+y2)|,|(x1−y1)−(x2−y2)|)
若原来两点曼哈顿距离为x1−x2+y1−y2或x2−x1+y2−y1时，都可以表示为|(x1+y2)−(x2+y2)|
若原来两点曼哈顿距离为x1−x2+y2−y1或x2−x1+y1−y2时，都可以表示为|(x1−y1)−(x2−y2)|
将每一个点(x,y)转化为(x+y,x−y)，新坐标系下的切比雪夫距离即为原坐标系下曼哈顿距离。
那么转化回去，道理也是相同的。
详细看参考代码。
参考代码：

class Solution {
public:
    /**
     * 
     * @param n int整型 
     * @param a int整型二维数组 
     * @param aRowLen int a数组行数
     * @param aColLen int* a数组列数
     * @return long长整型
     */
    long long x[100005],y[100005],ans=1ll<<61;
    long long sumx[100005],sumy[100005],xx[100005],yy[100005];
    long long wwork(int n, int** a, int aRowLen, int* aColLen) {
        // write code here
        for (int i=1;i<=n;i++)
        {
            xx[i]=a[i-1][0];
            yy[i]=a[i-1][1];
            x[i]=xx[i]+yy[i];
            y[i]=xx[i]-yy[i];
            xx[i]=x[i];
            yy[i]=y[i];
        }
        x[0]=0;
        y[0]=0;
        sort(x+1,x+1+n);
        sort(y+1,y+1+n);
        for (int i=0;i<=n;i++)
        {
            sumx[i]=0;
            sumy[i]=0;
        }
        for (int i=1;i<=n;i++)
        {
            sumx[i]=sumx[i-1]+x[i];
            sumy[i]=sumy[i-1]+y[i];
        }
        for (int i=1;i<=n;i++)
        {
            long long ans1=0,pos=0;
            pos=lower_bound(x+1,x+n+1,xx[i])-x;
            ans1+=(xx[i]*pos-sumx[pos])+((sumx[n]-sumx[pos])-xx[i]*(n-pos));
            pos=lower_bound(y+1,y+n+1,yy[i])-y;
            ans1+=(yy[i]*pos-sumy[pos])+((sumy[n]-sumy[pos])-yy[i]*(n-pos));
            ans=min(ans,ans1);
        }
        return ans/2;
    }
};