题意
求一个点，到所有点的切比雪夫距离之和最小。
题解
切比雪夫转曼哈顿+前缀和 显然切比雪夫不便于求和，因为它是一个max套在最外层，如果转为曼哈顿的形式就成了加加减减的问题了。 回忆一下转换公式：(x,y)->((x+y)/2,(x-y)/2) 答案是，关键是去绝对值符号，也就是。y同理。 不妨分开x和y来处理，把x和y分别排序，然后统计一波前缀和sx，sy。 枚举一个点(x0,y0)，在x中找到比它小的数的个数px，大的自然可以知道n-px。此时x的距离就是sx[n]-sx[px]-(n-px)*a[i].x) + ((px-1)*a[i].x-sx[px-1]。y同理。
代码
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const int MAXN=100010;
int n;
struct U{ll x,y;}a[MAXN];
ll x[MAXN],y[MAXN];
ll sum=0,sx[MAXN],sy[MAXN];
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
ll X,Y;
scanf("%lld%lld",&X,&Y);
x[i]=X+Y;y[i]=X-Y;
a[i]=(U){x[i],y[i]};
sum+=x[i]+y[i];
}
sort(x+1,x+n+1);sort(y+1,y+n+1);
for(int i=1;i<=n;i++)
{
sx[i]=sx[i-1]+x[i];
sy[i]=sy[i-1]+y[i];
}
ll ans=1ll<<60;
for(int i=1;i<=n;i++)
{
int px=lower_bound(x+1,x+n+1,a[i].x)-x;
int py=lower_bound(y+1,y+n+1,a[i].y)-y;
ll tmp=(sx[n]-sx[px]-(n-px)*a[i].x) + ((px-1)*a[i].x-sx[px-1])
+(sy[n]-sy[py]-(n-py)*a[i].y) + ((py-1)*a[i].y-sy[py-1]);
ans=min(ans,tmp);
}
printf("%lld\n",ans/2);
return 0;
}
