本文主要是介绍hdu-4666-Hyperspace-最长曼哈顿距离，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：
给定一些操作（0代表添加一个点，1代表删除一个点），求这些点的最远曼哈顿距离。
做法：
只考虑二维空间上两个坐标之间的曼哈顿距离(x1, y1) 和 (x2, y2)，|x1-x2| +|y1-y2|去掉绝对值符号后共有下列四种情况
(x1-x2) + (y1-y2), (x1-x2) + (y2-y1), (x2-x1) + (y1-y2), (x2-x1) + (y2-y1)
转化一下：
(x1+y1) - (x2+y2), (x1-y1) - (x2-y2), (-x1+y1) - (-x2+y2), (-x1-y1) - (-x2-y2)
显然，任意给两个点，我们分别计算上述四种情况，那么最大值就是曼哈顿距离。
转化后，“-”号两侧的坐标形式是一样的。维数为5，因此我们可以用二进制枚举。
最大曼哈顿距离 = max{每种情况下的最大值-最小值}；
用multiset存储每种情况的值。
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<set>
using namespace std;
#define maxn 60002
int maps[maxn][6];
multiset<int>se[1<<5];
multiset<int>::iterator i1,i2;
int main()
{int i,j,leap,x,n,m,a;while(~scanf("%d%d",&n,&m)){for(i=0;i<(1<<5);i++)se[i].clear();for(i=1;i<=n;i++){scanf("%d",&leap);if(leap==0){for(j=0;j<m;j++){scanf("%d",&maps[i][j]);}for(a=0;a<(1<<m);a++){int as;as=0;for(j=0;j<m;j++){if(a&(1<<j))as+=maps[i][j];else as-=maps[i][j];}se[a].insert(as);}}else{scanf("%d",&x);for(a=0;a<(1<<m);a++){int as;as=0;for(j=0;j<m;j++){if(a&(1<<j))as+=maps[x][j];else as-=maps[x][j];}i1=se[a].find(as);se[a].erase(i1);}}int ans=0;for(a=0;a<(1<<m);a++){i1=se[a].begin();i2=se[a].end();i2--;ans=max(ans,(*i2)-(*i1));}cout<<ans<<endl;}}return 0;
}
这篇关于hdu-4666-Hyperspace-最长曼哈顿距离的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
