本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-04-28 15:30:30
题目
考察：思维。
题目简述：
定义 $\text{dist}(A,B)$ 表示：
- 一开始它在 $A$ 点。
- 设 $A$ 点坐标为 $(x,y)$，然后它可以向 $(x+1,y+1),(x+1,y-1),(x-1,y-1),(x-1,y+1)$ 移动一步，$\text{dist}(A,B)$ 为移动的最小步数。
- 当其永远无法达到时，$\text{dist}(A,B)=0$。
给你 $n$ 个点，其坐标分别为 $A_i$，求 $\displaystyle\sum_{i=1}^{n-1}\sum_{j=i+1}^n\text{dist}(A_i,A_j)$。
我们很容易分析出 $\text{dist}((x_i,y_i),(x_j,y_j))=\max(x_i-x_j,y_i-y_j)$，在 $(x_i+y_i)\bmod 2\ne(x_j+y_j)\bmod 2$ 时，$\text{dist}((x_i,y_i)(x_j,y_j))=0$。
暴力模拟的话，时间复杂度为 $O(n^2)$，无法通过 $n\le 2\times 10^5$ 的数据。
我们可以尝试把他转化成曼哈顿距离，如图：
我们将其旋转 $45$ 度，使 $(0,0)$ 还是 $(0,0)$，这样 $(0,2)$ 变成了 $(-1,1)$。
我们很容易发现 $(x,y)$ 变成了 $\displaystyle(\frac{x_i+y_i}{2},\frac{y_i-x_i}{2})$。
以上是 $(x_i+y_i)\bmod 2=0$ 的情况，$(x_i+y_i)\bmod 2=1$ 时我们只需要让 $y_i$ 减去 $1$ 就可以了。
这样，式子就变成了 $\displaystyle\sum_{i=1}^{n-1}\sum_{j=i+1}^n|x_i-x_j|+|y_i-y_j|$，那么我们可以排一个序（值是不变的），然后：
$$\sum_{i=1}^{n-1}\sum_{j=i+1}^nx_j+y_j-x_i-y_i=\sum_{j=2}^n\sum_{i=1}^{j-1}x_j+y_j-x_i-y_i$$
然后我们可以维护前缀和（$\displaystyle sumx_x=\sum_{i=1}^xx_i,sumy_x=\sum_{i=1}^xy_i$），这样：
$$\sum_{j=2}^n\sum_{i=1}^{j-1}x_j+y_j-x_i-y_i=\sum_{j=2}^n(j-1)(x_j+y_j)-sumx_{j-1}-sumy_{j-1}$$
这样就可以了。
代码：
#include<bits\/stdc++.h>
#define int long long
#define inl inline
#define INF LLONG_MAX
#define rep(i,x,y) for(int i=x;i<=y;++i)
#define rer(i,x,y,cmp) for(int i=x;i<=y&&cmp;++i)
#define per(i,x,y) for(int i=x;i>=y;--i)
#define FAST ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define endl '\n'
using namespace std;
const int N=4e5+5;
int n,x[N],y[N],ans;
vector<int>gx[5],gy[5];
signed main(){
FAST;
cin>>n;
rep(i,1,n) cin>>x[i]>>y[i];
rep(i,1,n){
int k=(x[i]^y[i])&1;
gx[k].push_back((x[i]+y[i]-k)>>1);
gy[k].push_back((y[i]-x[i]-k)>>1);
}
rep(i,0,1){
sort(gx[i].begin(),gx[i].end());
sort(gy[i].begin(),gy[i].end());
}
rep(k,0,1){
int sumx=0,sumy=0,siz=gx[k].size();
rep(i,0,siz-1){
int x=gx[k][i],y=gy[k][i];
ans+=x*i-sumx+y*i-sumy;
sumx+=x;
sumy+=y;
}
}
cout<<ans;
return 0;
}
注：图中省略了一些距离，但结果相同。
鲁ICP备2025150228号