做网站需要知道什么软件运营怎么做

Link:

BZOJ 3170 传送门

Solution:

$Knowledge Point:$

切比雪夫距离$DIST(a,b)=max\{ |X'_a-X'_b|,|Y'_a-Y'_b|\}$

曼哈顿距离$dist(a,b)=|X_a-X_b|+|Y_a-Y_b|$

 

可以发现此题如果为曼哈顿距离，直接排2次序算前缀和就行了

接下来只要实现切比雪夫距离向曼哈顿距离的转换即可

可以将上述两种距离进行转化：

$DIST(a,b)=max\{ X'_a-X'_b,            Y'_a-Y'_b,            Y'_b-Y'_a,            X'_b-X'_a\}$

$dist(a,b)=max\{ X_a-X_b+Y_a-Y_b,X_a-X_b-Y_a+Y_b,-X_a+X_b+Y_a-Y_b,-X_a+X_b-Y_a+Y_b\}$

 

发现了奥妙重重的性质：只要将$X'$改为$X+Y$，$Y'$改为$X-Y$，两式就完全相同了

于是已知$X'$与$Y'$时，$X=\frac{X'+Y'}{2}$，$Y=\frac{X'-Y'}{2}$

使用新点和曼哈顿距离解题即可

 

Code:

#include <bits/stdc++.h>using namespace std;
typedef long long ll;
const int MAXN=1e5+10;
struct data{ll x,y;int id;}dat[MAXN];
int n;ll pre[MAXN],res[MAXN];bool cmp1(data a,data b){return a.x<b.x;}
bool cmp2(data a,data b){return a.y<b.y;}int main()
{scanf("%d",&n);for(int i=1;i<=n;i++){ll x,y;scanf("%lld%lld",&x,&y);dat[i].id=i;dat[i].x=(x+y);dat[i].y=(x-y);}sort(dat+1,dat+n+1,cmp1);for(int i=1;i<=n;i++) pre[i]=pre[i-1]+dat[i].x;for(int i=1;i<=n;i++) res[dat[i].id]=(pre[n]-pre[i])-dat[i].x*(n-2*i+1)-pre[i-1];sort(dat+1,dat+n+1,cmp2);for(int i=1;i<=n;i++) pre[i]=pre[i-1]+dat[i].y;for(int i=1;i<=n;i++)res[dat[i].id]+=(pre[n]-pre[i])-dat[i].y*(n-2*i+1)-pre[i-1];for(int i=2;i<=n;i++) res[1]=min(res[1],res[i]);printf("%lld",res[1]>>1);return 0;
}