自动搬运

查看原文

来自洛谷，原作者为

	LiWenX 4587

搬运于2025-08-24 21:49:00，当前版本为作者最后更新于2024-08-15 15:29:49，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

来点无脑做法。

首先把切比雪夫距离转化成曼哈顿距离。

具体来说，对于点 $(x_1,y_1)$ 与 $(x_2,y_2)$ 的切比雪夫距离等于点 $(\frac{x_1+y_1}{2},\frac{x_1-y_1}{2})$ 与 $(\frac{x_2+y_2}{2},\frac{x_2-y_2}{2})$ 的曼哈顿距离。

那么现在可以把所有点 $(x_i,y_i)$ 换成 $(x_i+y_i,x_i-y_i)$，问题就变成了找一个点，使得曼哈顿距离最小，注意我这里是没有除以二的，最后要除回去才对。

变成曼哈短距离最大的好处就是把横纵坐标的 $\max$ 换成了加法，这使得我们可以横纵坐标分别考虑。

先做答案的横坐标 $x$，那么纵坐标问题是对称的，我们现在只考虑横坐标咋做，我们要最小化：

直接把 $k_i$ 看做是有 $k_i$ 个 $x_i$，那么就是数轴上有若干个点，我们要求一个点使得到所有点的距离之和最小，根据初中数学老师告诉我们的结论，直接取中间的那个点即可，证明还是很简单的，可以考虑若干个绝对值函数加起来，最小值必然在斜率为 $0$ 的点上，那么这个点必然是中点。

于是就做完了。

但是还有一个问题，最后复原答案的时候有一步要除一个 $2$，这样可能会使得和真实的答案相差 $O(1)$ 个位置，直接暴力判断周围距离不超过 $2$ 的点中最优的那一个即可。

代码如下：

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n;
struct node{
	int x,k;
}a[100005],b[100005];
int x[100005],y[100005],k[100005];
signed main(){
	cin>>n;
	__int128 s=0;
	for(int i=1;i<=n;i++){
		cin>>x[i]>>y[i]>>k[i];
		s+=k[i];
		a[i].x=x[i]+y[i];
		b[i].x=x[i]-y[i];
		a[i].k=b[i].k=k[i];
	}
	sort(a+1,a+1+n,[](node x,node y){
		return x.x<y.x;
	});
	sort(b+1,b+1+n,[](node x,node y){
		return x.x<y.x;
	});
	int pos1=0,pos2=0,t=0;
	for(int i=n;i;i--){
		t+=a[i].k;
		if(t*2>=s){
			pos1=a[i].x;
			break;
		}
	}
	t=0;
	for(int i=n;i;i--){
		t+=b[i].k;
		if(t*2>=s){
			pos2=b[i].x;
			break;
		}
	}
	int X=pos1+pos2;
	int Y=pos1-pos2;
	X>>=1,Y>>=1;
	__int128 minn=1e30;
	int ansx=0,ansy=0;
	for(int i=-2;i<=2;i++){
		for(int j=-2;j<=2;j++){
			if(X+i<1||X+i>5e8||Y+j<1||Y+j>5e8) continue;
			s=0;
			for(int p=1;p<=n;p++){
				s+=max(abs(X+i-x[p]),abs(Y+j-y[p]))*k[p];
			}
			if(s<minn){
				minn=s;
				ansx=X+i;
				ansy=Y+j;
			}
		}
	}
	cout<<ansx<<' '<<ansy<<'\n'; 
}