pro： 有N个小松鼠，它们的家用一个点x,y表示，两个点的距离定义为：点(x,y)和它周围的8个点即上下左右四个点和对角的四个点，距离为1。现在N个松鼠要走到一个松鼠家去，求走过的最短距离。0<=N<=10^5 ，-10^9<=x,y<=10^9
sol： 常识告诉我们，8个反向距离相同，等价于切比雪夫距离。 为了方便统计距离，转化为曼哈顿距离。 此题是找一只松鼠家作为中心点，所以不是分别求中位数。
而是枚举每个松鼠，快速计算其他松鼠到他的距离，而快速统计只需要分类正负即可。
#include<bits/stdc++.h> #define ll long long #define rep(i,a,b) for(int i=a;i<=b;i++) using namespace std; const int maxn=400010; int x[maxn],y[maxn];ll sum[maxn],ans; ll sumx[maxn],sumy[maxn]; struct point{ int x,y;}s[maxn]; bool cmpx(point w,point v){ return w.x<v.x; } bool cmpy(point w,point v){ return w.y<v.y; } int main() { int N; scanf("%d",&N); rep(i,1,N){ ll tx,ty; scanf("%d%d",&tx,&ty); s[i].x=tx+ty; s[i].y=tx-ty; } sort(s+1,s+N+1,cmpx); rep(i,1,N) x[i]=s[i].x,sumx[i]=sumx[i-1]+s[i].x; sort(s+1,s+N+1,cmpy); rep(i,1,N) y[i]=s[i].y, sumy[i]=sumy[i-1]+s[i].y; rep(i,1,N) { ll tmp=0; int pos; pos=lower_bound(x+1,x+N+1,s[i].x)-x; tmp+=1LL*(pos-1)*s[i].x-sumx[pos-1]+(sumx[N]-sumx[pos-1])-1LL*(N-pos+1)*s[i].x; pos=lower_bound(y+1,y+N+1,s[i].y)-y; tmp+=1LL*(pos-1)*s[i].y-sumy[pos-1]+(sumy[N]-sumy[pos-1])-1LL*(N-pos+1)*s[i].y; if(i==1) ans=tmp; else ans=min(ans,tmp); } cout<<ans/2<<endl; return 0; }