BZOJ3170：[TJOI2013]松鼠聚会

题目传送门：https://lydsy.com/JudgeOnline/problem.php?id=3170

通过分析可以发现，题目所说的两点之间的距离就是切比雪夫距离。

两点之间欧几里得距离：\(\sqrt{(x_1-x_2)^2+(y_1-y_2)^2}\)

两点之间曼哈顿距离：\(|x_1-x_2|+|y_1+y_2|\)

两点之间切比雪夫距离：\(max(|x1-x2|,|y1-y2|)\)

曼哈顿距离转切比雪夫距离：\((x,y)--->(x+y,x-y)\)

切比雪夫距离转曼哈顿距离：\((x,y)--->(\frac{x+y}{2},\frac{x-y}{2})\)

由于一个点到多个点的曼哈顿距离可以通过前缀和后缀和\(O(1)\)求，而切比雪夫只能\(O(n)\)求，所以我们这题只需要把坐标转化一下求曼哈顿距离即可。为了避免\(double\)，转坐标的时候不除二，最后答案再除二。

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

空间复杂度：\(O(n)\)

代码如下：

#include <cstdio>

#include <algorithm>

using namespace std;

typedef long long ll;

const int maxn=1e5+5;

int n;ll res=1e18;

ll sum_pre[maxn],sum_suf[maxn],ans[maxn];

int read() {

	int x=0,f=1;char ch=getchar();

	for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;

	for(;ch>='0'&&ch<='9';ch=getchar())x=x*10+ch-'0';

	return x*f;

}

struct point {

	int x,y,id;

}p[maxn];

bool cmp_x(point a,point b) {return a.x<b.x;}

bool cmp_y(point a,point b) {return a.y<b.y;}

int main() {

	n=read();

	for(int i=1;i<=n;i++) {

		int x=read(),y=read();

		p[i].x=x+y,p[i].y=x-y;

		p[i].id=i;

	}

	sort(p+1,p+n+1,cmp_x);

	for(int i=n;i;i--)

		sum_suf[i]=sum_suf[i+1]+p[i].x;

	for(int i=1;i<=n;i++) {

		sum_pre[i]=sum_pre[i-1]+p[i].x;

		if(i!=1)ans[p[i].id]=1ll*p[i].x*(i-1)-sum_pre[i-1];

		if(i!=n)ans[p[i].id]+=sum_suf[i+1]-1ll*p[i].x*(n-i);

	}

	sort(p+1,p+n+1,cmp_y);

	for(int i=n;i;i--)

		sum_suf[i]=sum_suf[i+1]+p[i].y;

	for(int i=1;i<=n;i++) {

		sum_pre[i]=sum_pre[i-1]+p[i].y;

		if(i!=1)ans[p[i].id]+=1ll*p[i].y*(i-1)-sum_pre[i-1];

		if(i!=n)ans[p[i].id]+=sum_suf[i+1]-1ll*p[i].y*(n-i);

		res=min(res,ans[p[i].id]>>1);

	}

	printf("%lld\n",res);

	return 0;

}

巴特西

BZOJ3170：[TJOI2013]松鼠聚会

最新文章

热门文章