51nod 3148 松鼠聚会

题目链接：https://www.51nod.com/Challenge/ProblemSubmitDetail.html#judgeId=1019746
因为可以向8个方向走，然后一个点到另外一个点在可以走8个方向的情况下，他们的最小值就是切比雪夫距离。然后我们可以转化为一个点到其他所有点的切比雪夫距离和。不能直接求切比雪夫距离，在二维平面我们可以通过转换坐标将切比雪夫距离转化为曼哈顿距离。
如果枚举一个点x[i],y[i]。在x轴他到其他点的距离 ：

x[i]-x[1]+x[i]-x[2]...x[i]-x[i-1]+x[i+1]-x[i]+...x[n]-x[i].

我们可以进一步化简

i*x[i]-sum[i]+sum[n]-sum[i]-(n-i)x[i];

y轴也是这样。
然后我们就可以遍历查询一遍求最小了.(因为直接(x+y)/2,在处理的时候可能会出现小数最后结果在除以2.我直接转化结果wa了...)

#include<bits/stdc++.h>
#define fp(i,a,b) for(int i=a;i<=b;i++)
typedef long long ll;
typedef double dl;
using namespace std;

const int N=2e5+7;
const ll M=1e9+7;
const int INF=0x3f3f3f3f;

int n,m;

struct node{
    ll x,y;
}s[N];
ll x[N],y[N];
ll prex[N],prey[N];
void solve()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)    
    {
        int X,Y;
        scanf("%d%d",&X,&Y);//求切比雪夫距离
        x[i]=s[i].x=(X+Y);
        y[i]=s[i].y=(X-Y); 
    }
    sort(x+1,x+1+n);
    sort(y+1,y+1+n);
    for(int i=1;i<=n;i++)
    {
        prex[i]=prex[i-1]+x[i];
        prey[i]=prey[i-1]+y[i];
    }
    ll ans=1e18;
    for(int i=1;i<=n;i++)
    {
        ll res=0;
        int posx=lower_bound(x+1,x+n+1,s[i].x)-x;
        res+=prex[n]-prex[posx]-(n-posx)*s[i].x+posx*s[i].x-prex[posx];
        int posy=lower_bound(y+1,y+n+1,s[i].y)-y;
        res+=prey[n]-prey[posy]-(n-posy)*s[i].y+posy*s[i].y-prey[posy];
        ans=min(ans,res);
    }
    printf("%lld",ans/2);

}

int main()
{
    //ios::sync_with_stdio(0);
    //cin.tie(0),cout.tie(0);
    //int T; scanf("%d",&T)
    //for(int i=1;i<=T;i++)
        solve();
}