BZOJ 3170 松鼠聚会(切比雪夫距离转曼哈顿距离)

时间:2024-01-18 20:25:14

题意

有N个小松鼠,它们的家用一个点x,y表示,两个点的距离定义为:点(x,y)和它周围的8个点即上下左右四个点和对角的四个点,距离为1。现在N个松鼠要走到一个松鼠家去,求走过的最短距离。

思路

题目中的距离是切比雪夫距离,而切比雪夫距离与曼哈顿距离可以互相转化。

考虑二维笛卡尔坐标系的坐标原点\(O(0,0)\),与它的切比雪夫距离为1的点的集合形成的图形是一个边长为2的正方形,与它的曼哈顿距离为1的点的集合形成的图形是一个边长为1的正方形,如果把这个边长为2的正方形旋转45度再缩小2倍,两个图形即可重合。

于是对应与点之间的关系,\((x,y)\)对应与\((\frac{x+y}{2},\frac{x-y}{2})\)。为了避免浮点数,我们把点的坐标再乘2。这样,切比雪夫距离就变成了曼哈顿距离了。

现在考虑枚举要汇合的那个点,因为曼哈顿距离为\(\left|x1-x2\right|+\left|y1-y2\right|\)。所以可以对x,y坐标单独考虑。

预处理出x坐标的前缀和和后缀和,这样\(\sum(x-x_i)=\sum x-\sum x_i\)

y坐标同理。

因为坐标范围比较大,需要对坐标进行离散化

时间复杂度\(O(nlogn)\)。

代码

# include<bits/stdc++.h>
using namespace std;
# define lowbit(x) ((x)&(-x))
# define pi acos(-1.0)
# define eps 1e-8
# define MOD 100000007
# define INF 1e16
# define mem(a,b) memset(a,b,sizeof(a))
# define FOR(i,a,n) for(register int i=a; i<=n; ++i)
# define FDR(i,a,n) for(register int i=a; i>=n; --i)
# define bug puts("H");
# define lch p<<1,l,mid
# define rch p<<1|1,mid+1,r
# define mp make_pair
# define pb push_back
typedef pair<int,int> PII;
typedef vector<int> VI;
# pragma comment(linker, "/STACK:1024000000,1024000000")
typedef long long LL;
inline char nc(){
static char buf[1000000],*p1=buf,*p2=buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++;
}
inline int Scan(){
char ch=nc();int sum=0, f=1;
if (ch=='-') f=-1, ch=nc();
while(!(ch>='0'&&ch<='9'))ch=nc();
while(ch>='0'&&ch<='9')sum=sum*10+ch-48,ch=nc();
return sum*f;
}
const int N=100005;
//Code begin.... struct Node{LL x, y;}node[N];
vector<LL>v1, v2;
LL Xsum1[N], Xsum2[N], Ysum1[N], Ysum2[N];
int Cx1[N], Cx2[N], Cy1[N], Cy2[N]; int main ()
{
int n;
LL x, y;
scanf("%d",&n);
FOR(i,1,n) {
scanf("%lld%lld",&x,&y);
node[i].x=x+y; node[i].y=x-y;
v1.pb(node[i].x); v2.pb(node[i].y);
}
sort(v1.begin(),v1.end()); sort(v2.begin(),v2.end());
int pos1=0, pos2=0;
FOR(i,0,n-1) {
if (i==0||v1[i]!=v1[i-1]) Xsum1[++pos1]=Xsum1[pos1-1]+v1[i], Cx1[pos1]=Cx1[pos1-1]+1;
else Xsum1[pos1]+=v1[i], ++Cx1[pos1];
if (i==0||v2[i]!=v2[i-1]) Ysum1[++pos2]=Ysum1[pos2-1]+v2[i], Cy1[pos2]=Cy1[pos2-1]+1;
else Ysum1[pos2]+=v2[i], ++Cy1[pos2];
}
FDR(i,n-1,0) {
if (i==n-1||v1[i]==v1[i+1]) Xsum2[pos1]+=v1[i], ++Cx2[pos1];
else Xsum2[--pos1]=Xsum2[pos1+1]+v1[i], Cx2[pos1]=Cx2[pos1+1]+1;
if (i==n-1||v2[i]==v2[i+1]) Ysum2[pos2]+=v2[i], ++Cy2[pos2];
else Ysum2[--pos2]=Ysum2[pos2+1]+v2[i], Cy2[pos2]=Cy2[pos2+1]+1;
}
int siz1=unique(v1.begin(),v1.end())-v1.begin();
int siz2=unique(v2.begin(),v2.end())-v2.begin();
LL ans=1e16, tmp;
FOR(i,1,n) {
int idx=lower_bound(v1.begin(),v1.begin()+siz1,node[i].x)-v1.begin()+1;
int idy=lower_bound(v2.begin(),v2.begin()+siz2,node[i].y)-v2.begin()+1;
tmp=(node[i].x*Cx1[idx]-Xsum1[idx])+(Xsum2[idx+1]-node[i].x*Cx2[idx+1])+(node[i].y*Cy1[idy]-Ysum1[idy])+(Ysum2[idy+1]-node[i].y*Cy2[idy+1]);
ans=min(ans,tmp);
}
printf("%lld\n",ans/2);
return 0;
}