POJ-2926 Requirements(最远曼哈顿距离)
程序员文章站
2022-04-03 23:19:19
...
**题目:http://poj.org/problem?id=2926
题意:求五维空间最远曼哈顿距离.
思路:曼哈顿距离:dis = |x1-x2|+|y1-y2|
切比雪夫距离:dis = max(|x1-x2|,|y1-y2|)
求曼哈顿距离若去掉绝对值,即在以下4项中选择最大值.
(x1-x2)+(y1-y2)
(-x1+x2)+(y1-y2)
(x1-x2)+(-y1+y2)
(-x1+x2)+(-y1+y2)
再转化一下
(x1+y1)-(x2+y2)
(-x1+y1)-(-x2+y2)
(x1-y1)-(x2-y2)
(-x1-y1)-(-x2-y2)
即上面这四项的最大值,也就是肯定尽量使减号左边尽量大,右边尽量小
而且我们发现减号两边的式子的格式都是一样的,而且只跟一个点有关系,所以我们可以维护一下最大最小值即可
mark:曼哈顿最小生成树 https://blog.csdn.net/huzecong/article/details/8576908
代码:
#include<cstdio>
#include<iostream>
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f;
const int maxn = 2e5+5;
const double eps = 1e-8;
int n;
double a[maxn][6];
double b[123][2];
double solve()
{
for(int j = 0;j< 1<<5;j++) b[j][0] = -1e15,b[j][1] = 1e15;
for(int i = 1;i<= n;i++)
{
for(int j = 0;j< (1<<5);j++)//枚举所有加减状态
{
double tmp = 0;
for(int k = 0;k< 5;k++)//1为+,0为-
{
if(j&(1<<k)) tmp+= a[i][k];
else tmp-= a[i][k];
}
b[j][0] = max(b[j][0],tmp);
b[j][1] = min(b[j][1],tmp);
}
}
double ans = 0;
for(int i = 0;i< 1<<5;i++) ans = max(ans,b[i][0]-b[i][1]);
return ans;
}
int main()
{
cin>>n;
for(int i = 1;i<= n;i++)
for(int j = 0;j< 5;j++)
scanf("%lf",&a[i][j]);
double ans = solve();
printf("%.2f\n",ans);
return 0;
}