题目大意
\(有n个d维空间的点，求其中曼哈顿距离最大的两点之间的曼哈顿距离\)\
数据范围
\(2\le n\le10^6,1\le d\le 4\)
\(这题的贪心思路需要用到曼哈顿距离的特性\)
点这里
\(重新回到这道题，先利用此性质思考1维，即数轴\)
\(可以发现只要在数轴非常左边的地方取一点P,即可使得对于任意两点A,B\)
\(P都在A,B同侧，所以AB=|PA-PB|，求AB最大值，只需使得PA最大,PB最小\)
\(可以O(n)求出最大值和最小值再相减\)
\(考虑向2维推广，同样构造坐标足够小(或大)的点使得其在两点同侧\)
\(可以把2维空间看成两条斜着的数轴，于是可以在两条数轴的极左端建立两个点P1,P2\)
\(此时对于任意两点A,B,如果P1在A,B同侧，则满足条件，可以得出AB\)
\(如果P1不在A,B同侧，则计算出的值小于AB，但是此时P2一定在A,B同侧\)
\(仍然可以得出正确答案\)
\(于是可以和1维一样做，并对两点求出的值取max\)
\(可以得出对于n维空间，只需2^{n-1}个P点即可使得对于任意两点A,B都有一个P点在它们同侧\)
\(附上代码\)
点击查看代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,d,ans,l,r;
const int N=1000000;
struct dian
{
int a[4];
}g[1000009];
int mhd(int x,int y)
{
int now=0;
for(int i=0;i<d;i++)
now+=abs(g[x].a[i]-g[y].a[i]);
return now;
}
int minn[9],maxn[9];
signed main()
{
cin>>n>>d;
memset(minn,0x3f3f3f3f,sizeof(minn));
g[N+1].a[0]=1e9;
g[N+1].a[1]=1e9;
g[N+1].a[2]=1e9;
g[N+1].a[3]=1e9;
g[N+2].a[0]=1e9;
g[N+2].a[1]=-1e9;
g[N+2].a[2]=1e9;
g[N+2].a[3]=1e9;
g[N+3].a[0]=1e9;
g[N+3].a[1]=1e9;
g[N+3].a[2]=-1e9;
g[N+3].a[3]=1e9;
g[N+4].a[0]=1e9;
g[N+4].a[1]=-1e9;
g[N+4].a[2]=-1e9;
g[N+4].a[3]=1e9;
g[N+1+4].a[0]=1e9;
g[N+1+4].a[1]=1e9;
g[N+1+4].a[2]=1e9;
g[N+1+4].a[3]=-1e9;
g[N+2+4].a[0]=1e9;
g[N+2+4].a[1]=-1e9;
g[N+2+4].a[2]=1e9;
g[N+2+4].a[3]=-1e9;
g[N+3+4].a[0]=1e9;
g[N+3+4].a[1]=1e9;
g[N+3+4].a[2]=-1e9;
g[N+3+4].a[3]=-1e9;
g[N+4+4].a[0]=1e9;
g[N+4+4].a[1]=-1e9;
g[N+4+4].a[2]=-1e9;
g[N+4+4].a[3]=-1e9;
for(int i=1;i<=n;i++)
{
for(int j=0;j<d;j++)
scanf("%lld",&g[i].a[j]);
for(int j=1;j<=8;j++)
{
minn[j]=min(minn[j],mhd(N+j,i));
maxn[j]=max(maxn[j],mhd(N+j,i));
}
}
for(int i=1;i<=(1<<(d-1));i++)
{
ans=max(ans,maxn[i]-minn[i]);
}
cout<<ans;
return 0;
}