题意
求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)的复杂度了.
思考优化的时候注意观察最优解的分布, 缩小比较范围.
#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
", ans);
}
return 0;
}