]Requirements[最远曼哈顿距离]

发布时间:2016-12-9 13:59:33 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"]Requirements[最远曼哈顿距离]",主要涉及到]Requirements[最远曼哈顿距离]方面的内容,对于]Requirements[最远曼哈顿距离]感兴趣的同学可以参考一下。

[poj 2926]Requirements[最远曼哈顿距离] 分类: 计算几何2013-08-31 19:15 13人阅读 评论(0) 收藏 举报 目录(?)[+] 题意 求5维点中曼哈顿距离最远的两点间的曼哈顿距离. define the dissimilarity of two universities X and Y : |x1 − y1| + |x2 − y2| + |x3 − y3| + |x4 − y4| + |x5 − y5| (这里, 标号代表不同的维, 而字母代表不同的变量, 与下面二维的表示习惯正好相反) 思路 只考虑二维空间上两个坐标(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) 减号左边是第一个变量, 右边是第二个变量. 不同的维具有不同的状态, 可以用二进制枚举, 但由于是计算两个点之间的曼哈顿距离, 二元作差的形式不变. 对于一对点, 枚举所有的状态, 二者作差, 最大值代表他们的绝对值之和, 即曼哈顿距离. 而这个距离的最大值即为所求. 按照正常的思维: 1. 枚举点的所有二元组. 2. 求这两个点的曼哈顿距离:      枚举两个点所有的状态, 差值最大的那个状态就是可以构成绝对值的状态, 得到的数就是曼哈顿距离. 3. 选择所有这些距离中的最大值. 这样的话复杂度是 O(n^2), 略大. 但是注意到取了两次"最大", 而这两次"最大"经过分析可知, 是可以合并的.  因为在同一个状态下, 对于所有点, 最大值和最小值之差可以认为是"疑似绝对值". 虽说不一定是绝对值, 而是首先盲目地算了一个"最大值", 但是那个最大的绝对值一定在结果之中, 且是最大的那个(绝对值 > 非绝对值). 计算出所有的"疑似绝对值", 找出最大的, 就是"真绝对值", 并且是"真绝对值"中最大的(即符号错误不会使答案变小). 这样就是O(n)的复杂度了. 思考优化的时候注意观察最优解的分布, 缩小比较范围. [cpp] view plaincopy #include <cstdio>   #include <cstring>   #include <algorithm>   using namespace std;   #define N 100003   #define inf 1e100   double a[N][5];   int n;      int main() {       while (scanf("%d", &n) == 1) {           for (int i=0; i<n; i++)               for (int j=0; j<5; j++) scanf("%lf", &a[i][j]);           double ans = 0, mi, mx, t;           for (int s=0; s<(1<<5); s++) {               mi = inf, mx = -inf;               for (int i=0; i<n; i++) {                   t = 0;                   for (int j=0; j<5; j++)                       if ((1<<j) & s) t += a[i][j];                       else t -= a[i][j];                   mi = min(mi, t);                   mx = max(mx, t);               }               ans = max(ans, mx-mi);           }           printf("%.2lf\n", ans);       }       return 0;   }  

上一篇:UVA 11183 Teen Girl Squad (最小树形图,3级)
下一篇:cocos2d-x之TestCPP例子解析(2)-ActionsTest

相关文章

相关评论