曼哈顿距离和切比雪夫距离

前置知识(曼哈顿距离和切比雪夫距离)

曼哈顿距离： $ |x_1-x_2|+|y_1-y_2| $
切比雪夫距离： $ max(|x_1-x_2|,|y_1-y_2|)$
转换坐标：
曼哈顿距离 $ \to $ 切比雪夫距离：
$ (x,y) \to (x+y,x-y) $
切比雪夫距离 $ \to $ 曼哈顿距离： $ (x,y) \to (\frac{x+y}{2},\frac{x-y}{2}) $
原坐标的曼哈顿(切尔雪夫)距离=新坐标的切尔雪夫(曼哈顿)距离

例题

洛谷P3964松鼠聚会

题意：
给出多个坐标，选择一个坐标，使所有点到该坐标的切尔雪夫距离之和最小
思路： 切尔雪夫距离转换为曼哈顿距离求最小，转换坐标时先不除以2以免出现小数，最后答案再除以2
对于选定的一个点 $(x_j,y_j)$ ,求 $ \sum_{i=1}^n(|x_i-x_j|+|y_i-y_j|)$,可以用前缀和解决，以x为例，对于x坐标从小到大排序：
$\sum_{i=1}^n|x_i-x_j|=\sum_{i=1}^j(x_j-x_i)+\sum_{i=j+1}^n(x_i-x_j)=j \cdot x_j-\sum_{i=1}^jx_i+\sum_{j+1}^n-(n-j) \cdot x_j=(2j-n) \cdot x_j+\sum_{i=1}^nx_i-2 \cdot \sum_{i=1}^jx_i$
y同理，然后把算好的值映射回原来的坐标，全部遍历求min即可

struct node{
    ll pos,val;
    bool operator<(const node&tmp)const{
        return val<tmp.val;
    }
};
struct Z{
    ll posx,posy;
};
void solve() {
    ll n;
    cin>>n;
    vector<node> X(n+1),Y(n+1);
    vector<ll> sumx(n+1),sumy(n+1);
    vector<Z> A(n+1);
    for(int i=1;i<=n;i++){
        ll x,y;
        cin>>x>>y;
        X[i].val=(x+y);
        Y[i].val=(x-y);
        X[i].pos=Y[i].pos=i;
    }
    sort(X.begin()+1,X.end());
    sort(Y.begin()+1,Y.end());
    for(int i=1;i<=n;i++)sumx[i]=sumx[i-1]+X[i].val;
    for(int i=1;i<=n;i++)sumy[i]=sumy[i-1]+Y[i].val;
    for(int i=1;i<=n;i++)A[X[i].pos].posx=i;
    for(int i=1;i<=n;i++)A[Y[i].pos].posy=i;
    ll ans=1e18;
    for(int i=1;i<=n;i++){
        ll x=A[i].posx,y=A[i].posy;
        ll tmp=(2*x-n)*X[x].val+sumx[n]-2*sumx[x];
        tmp+=(2*y-n)*Y[y].val+sumy[n]-2*sumy[y];
        ans=min(ans,tmp);
    }
    cout<<ans/2<<'\n';
}

Heidi and the Turing Test (Medium)(扫描线+曼哈顿切尔雪夫转换)

查看题解