数学距离问题1

发表于 更新于 分类于 ， 阅读次数： Waline： 本文字数： 638 阅读时长 ≈ 2 分钟

题意：

给一个国际象棋中的“象”，但每次只能走一格，给N个点

计算总和 \(\displaystyle\sum_{i=1}^{N-1}\displaystyle\sum_{j=i+1}^N \text{dist}(P_i, P_j)\)​ 。

题解：

注意到实际上这样的走法将整个棋盘以\[x+y\]的奇偶划分为了二分图（更准确的讲，两个图），并且每两个可达点之间的最短距离公式如下： \[ dist(p_i,p_j) = max(|p_i.x - p_j.x|, |p_i.y-p_j.y|) \] 即两个点之间的切比雪夫距离。

证明如下，对于任意两个\(x+y\)奇偶性相同的顶点而言，设起始点为\((x,y)\)，目的点为\((xx,yy)\)设dx<dy即\(dist(p_i,p_j) = |p_i.y-p_j.y|\)。

\(xx=x+dx,yy=y+dy\)，则有\(dx = a-b，a+b=dy\)，根据定义可知\(dy=yy-y\)。

由以上公式,且x,y的奇偶性相同可知xx为在dx<dy下的所有可达点的横坐标。相反则同理，因此切比雪夫距离成立。

详细参考距离 - OI Wiki (oi-wiki.org)

如果你看懂了OIWiki中对切比雪夫定理的描述，以及其证明，并有坐标变换的基础，应该明白，切比雪夫距离是可以与曼哈顿距离相互转化的（仅仅切换了坐标系，即y=x函数为横坐标，y=-x函数为纵坐标。该说法很不完善，详细请看ioWiki，此处仅作简单说明，可以构造原坐标系函数y=x+b,x=y+a，则(a/2,b/2)为新坐标系下的坐标，读者可以尝试画图自己证明一下并不是很难）

上图(1,4) -> (1,3)

于是题目变为了求n个点的哈密顿距离之和，很经典的题。

由于曼哈顿距离是横纵坐标的距离和，我们只看单个坐标。

831c358c475935b97351ba39f7cf0fa9

coding。。。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
void slove() {
    cin>>n;

    for(int i=1;i<=n;i++) cin>>a[i].x>>a[i].y;

    for(int i=1;i<=n;i++) {
        if((a[i].x+a[i].y) %2==1)
            bx[1][++cn[1]] = a[i].x + a[i].y,by[1][cn[1]] = a[i].y - a[i].x;
        else
            bx[0][++cn[0]] = a[i].x + a[i].y,by[0][cn[0]] = a[i].y - a[i].x;
    }

    sort(bx[0]+1,bx[0]+1+cn[0]);
    sort(bx[1]+1,bx[1]+1+cn[1]);
    sort(by[0]+1,by[0]+1+cn[0]);
    sort(by[1]+1,by[1]+1+cn[1]);
    int ans = 0;
    for(int k =0;k<=1;k++) {
        int sum1 =0 ,sum2=0;
        for(int i=1;i<=cn[k];i++) {
            // cout<<k<<' '<<bx[k][i]<<' '<<by[k][i]<<endl;
            ans += (i-1) * (bx[k][i]+by[k][i]) - sum1-sum2;
            sum1 += bx[k][i];
            sum2 += by[k][i];
        }
    }
    cout<<ans/2<<endl;
}