洛谷5098——Cave Cows 3

发表于2023-09-04更新于2023-09-05阅读次数

给你 n 个二维坐标 (xi,yi)(x_i,y_i)，问你它们之间最大的曼哈顿距离是多少，即 max{∣x1−x2∣+∣y1−y2∣}max\{|x_1-x_2|+|y_1-y_2|\}。

n≤50000n\leq 50000

看到绝对值，尤其是这种两个绝对值相加的公式，一定要想到通过取 max 拿掉绝对值。

max{∣x1−x2∣+∣y1−y2∣}=max{x1−x2+y1−y2−x1+x2+y1−y2x1−x2−y1+y2−x1+x2−y1+y2}\begin{array}{l} max\{|x_1-x_2|+|y_1-y_2|\}\\ \begin{array}{ll} =max\{&x_1-x_2+y_1-y_2\\ &-x_1+x_2+y_1-y_2\\ &x_1-x_2-y_1+y_2\\ &-x_1+x_2-y_1+y_2\}\\ \end{array}\\ \end{array}

因为是求一个整体的大 max，所以可以先分别求每一项的 max，再把每一项的 max 合并得到总 max。容易发现，对于每一项 max，可以把每个点的两个坐标单独整理出来，例如

max{x1−x2+y1−y2}=max{x1+y1}+max{−x2−y2}max\{x_1-x_2+y_1-y_2\}=max\{x_1+y_1\}+max\{-x_2-y_2\}

对于其他 4 个 max 项也一样。

于是可以把每个点的 max 属性单独统计出，计算项的 max，再求出答案。

这题还有一个思路，就是把曼哈顿距离转成切比雪夫距离，也就是令 xi′=xi+yi,yi′=xi−yix'_i=x_i+y_i,y'_i=x_i-y_i，然后切比雪夫距离就是 max{∣xi′−xj′∣,∣yi′−yj′∣}max\{|x'_i-x'_j|,|y'_i-y'_j|\}。

求切比雪夫距离的最大值就简单多了，分别找出 x′,y′x',y' 的最大值和最小值，然后对应值做差再求最大值就可。

oiwiki 的评价是：两个不同的思路可以得到相同的代码，这很有趣。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<bits/stdc++.h>
using namespace std;
int n,x[51000],y[51000];
int mx[10];
int main(){
	cin.tie(0)->sync_with_stdio(false);
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>x[i]>>y[i];
	}
	for(int i=1;i<=n;i++){
		mx[1]=max(mx[1],x[i]+y[i]);
		mx[2]=max(mx[2],-x[i]+y[i]);
		mx[3]=max(mx[3],x[i]-y[i]);
		mx[4]=max(mx[4],-x[i]-y[i]);
	}
	int ans=max(mx[1]+mx[4],mx[2]+mx[3]);
	cout<<ans<<endl;
	return 0;
}