现在的位置: 首页 > 综合 > 正文

]Requirements[最远曼哈顿距离] [poj 2926]Requirements[最远曼哈顿距离]

2017年09月30日 ⁄ 综合 ⁄ 共 1713字 ⁄ 字号 评论关闭

[poj 2926]Requirements[最远曼哈顿距离]

分类: 计算几何 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)的复杂度了.

思考优化的时候注意观察最优解的分布, 缩小比较范围.

  1. #include <cstdio>  
  2. #include <cstring>  
  3. #include <algorithm>  
  4. using namespace std;  
  5. #define N 100003  
  6. #define inf 1e100  
  7. double a[N][5];  
  8. int n;  
  9.   
  10. int main() {  
  11.     while (scanf("%d", &n) == 1) {  
  12.         for (int i=0; i<n; i++)  
  13.             for (int j=0; j<5; j++) scanf("%lf", &a[i][j]);  
  14.         double ans = 0, mi, mx, t;  
  15.         for (int s=0; s<(1<<5); s++) {  
  16.             mi = inf, mx = -inf;  
  17.             for (int i=0; i<n; i++) {  
  18.                 t = 0;  
  19.                 for (int j=0; j<5; j++)  
  20.                     if ((1<<j) & s) t += a[i][j];  
  21.                     else t -= a[i][j];  
  22.                 mi = min(mi, t);  
  23.                 mx = max(mx, t);  
  24.             }  
  25.             ans = max(ans, mx-mi);  
  26.         }  
  27.         printf("%.2lf\n", ans);  
  28.     }  
  29.     return 0;  
  30. }  

抱歉!评论已关闭.