[TJOI2013]松鼠聚会
luogu P3964
首先容易得到两点间距离是\(max(|x_1-x_2|, |y_1-y_2|)\)（即切比雪夫距离）
然后有个套路：原\((x,y)\)求曼哈顿距离可以转换为\((x+y,x-y)\)求切比雪夫距离，同样的\((x,y)\)求切比雪夫距离就是求\((\frac{x+y}{2},\frac{x-y}{2})\)曼哈顿距离。
然后考虑优化求\(n-1\)个总曼哈顿距离的过程
先所有点以\(x,y\)分别作为关键字排序一遍，对于点\(i\)的\(sumx\)可得
\[(x_i-x_1)+(x_i-x_2)+\cdots+(x_i-x_i)+(x_{i+1}-x_i)+(x_{i+2}-x_i)+\cdots +(x_n-x_i)\\
i\times x_i-\sum^i_{j=1} x_j+\sum^n_{j=i+1} x_j-(n-i)\times x_i
\]
i\times x_i-\sum^i_{j=1} x_j+\sum^n_{j=i+1} x_j-(n-i)\times x_i
\]
\(sumy\)同理
不难发现我们维护一个前缀和即可。
另外为了防止坐标出现小数所以我们就不除2了，在最后答案的时候再除2
#include <cstdio>
#include <climits>
#include <algorithm>
#define MAXN 100010
#define ll long long
using namespace std;
int n;
struct nod{
int x,y;
} a[MAXN];
int sx[MAXN],sy[MAXN];
ll sumx[MAXN],sumy[MAXN];
int main(){
scanf("%d", &n);
for(int i=1;i<=n;++i){
int xx,yy;
scanf("%d %d", &xx, &yy);
a[i].x=xx+yy;
a[i].y=xx-yy;
sx[i]=a[i].x;
sy[i]=a[i].y;
}
sort(sx+1, sx+1+n);
sort(sy+1, sy+1+n);
for(int i=1;i<=n;++i) sumx[i]=sumx[i-1]+sx[i];
for(int i=1;i<=n;++i) sumy[i]=sumy[i-1]+sy[i];
ll ans=LLONG_MAX;
for(int i=1;i<=n;++i){
ll res=0;
int k=lower_bound(sx+1, sx+1+n, a[i].x)-sx;
res+=(ll)a[i].x*k-sumx[k]+sumx[n]-sumx[k]-(ll)(n-k)*a[i].x;
k=lower_bound(sy+1, sy+1+n, a[i].y)-sy;
res+=(ll)a[i].y*k-sumy[k]+sumy[n]-sumy[k]-(ll)(n-k)*a[i].y;
ans=min(ans, res);
}
printf("%lld", ans/2);
return 0;
}