模版-最长曼哈顿距离

本文主要是介绍模版-最长曼哈顿距离，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

只考虑二维空间上两个坐标之间的曼哈顿距离(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)

显然，任意给两个点，我们分别计算上述四种情况，那么最大值就是曼哈顿距离。

转化后，“-”号两侧的坐标形式是一样的。因此我们可以用二进制枚举。

最大曼哈顿距离 = max{每种情况下的最大值-最小值}；

用multiset<int>se[1<<n];存储每种情况的值，multiset里的第一个值即为最大值，最后一个值即为最小值。

最长的曼哈顿距离即为遍历每一种情况，max(*(se[i].begin)-*(se[i].end-1));

步骤：

1，读取点的坐标，然后把每一个点的二进制情况放在multiset里面。

for(j=0;j<m;j++)scanf("%d",&maps[i][j]);//m维空间，每个点对应每一个纬度的坐标值
for(a=0;a<(1<<m);a++)
{int 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);//加入对应的值
}

2，遍历所有对应的二进制情况，取最大值。

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;

这篇关于模版-最长曼哈顿距离的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---