BZOJ3170 [TJOI 2013]松鼠聚会
庆祝不知道什么时候已经刷题200+了……
Solution
首先,两个松鼠的家(x,y)、(x',y')之间的距离为max(|x-x'|,|y-y'|)。展开并变形,得到max(|(x+y)-(x'+y')|,|(x-y)-(x'-y')|)。令X=(x+y)/2,Y=(x-y)/2,则上式可化简为|X-X'|+|Y-Y'|,即曼哈顿距离形式。这样我们可以用 $\mathcal O(n)$ 的时间分别处理出每一个点的横、纵坐标与其他点之间横、纵坐标的距离之和。这样便可得到答案。
以上的变形如果有异议的话可以从曼哈顿距离的形式往回推。
另外,学习到曼哈顿距离的英文还可以叫做Taxicab_Geometry。
Code
#include <bits/stdc++.h> using namespace std; #define N 100005 int n; long long sum1[N],sum2[N],ans=1LL<<62; inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } struct O_o { long long p,x,y,dist; O_o(){} O_o(int _p):p(_p){ int a=read(),b=read(); x=a-b; y=a+b; } bool operator <(const O_o &a) const { return x<a.x; } }q[N]; int main() { cin>>n; for(int i=1;i<=n;i++) q[i]=O_o(i); sort(q+1,q+n+1); for(int i=2;i<=n;i++) sum1[i]=sum1[i-1]+(i-1)*(q[i].x-q[i-1].x); for(int i=n-1;i;i--) sum2[i]=sum2[i+1]+(n-i)*(q[i+1].x-q[i].x); for(int i=1;i<=n;i++) q[i].dist=sum1[i]+sum2[i], swap(q[i].x,q[i].y); sort(q+1,q+n+1); for(int i=2;i<=n;i++) sum1[i]=sum1[i-1]+(i-1)*(q[i].x-q[i-1].x); for(int i=n-1;i;i--) sum2[i]=sum2[i+1]+(n-i)*(q[i+1].x-q[i].x); for(int i=1;i<=n;i++) q[i].dist+=sum1[i]+sum2[i]; for(int i=1;i<=n;i++) ans=min(ans,q[i].dist); cout<<ans/2<<endl; }