【题目大意】
定义两个三元组I(xi, yi, zi)和J(xj, yj, zj)，他们的差为D(I, J) = max{xi - xj, yi - yj, zi - zj} - min{xi - xj, yi - yj, zi - zj}，给定n个三元组（n <= 200000），求任意两个三元组的差的和。
【题目分析】
数据范围非常大，枚举必然不可，需要数学方法。这个题目巧妙之处在于，模型经过了层层的包装，要想一下子有想法还真不容易。既然不能枚举了，这个max和min操作就不好办了，应该设法去掉。max{a, b, c} - min{a, b, c} = |a - b| + |b - c| + | c - a| / 2，这个公式应该不难想到，但是这只是第一步，因为引进了绝对值，依然不好做。可以先算出分子，最后再除2。接下来需要一个等价变换，以a - b为例，a - b = xi - xj - yi + yj = (xi - yi) - (xj - yj)，同理把b - c、c - a都写成这种形式。这一步变换看似作用不大，但是假设我们算出所有的xi - yi之后（i = 0... n - 1），将其排序，会发现，对于第i个xi - yi，它前面的都比它小，后面的都比它大。而实际上，由于求任意两个三元组的差，肯定xi - yi会和任意的xj - yj都作差的，加了绝对值后，它对最后的结果就会贡献i个(xi - yi)，n - i - 1个-(xi - yi)。同样的方法算出所有的(yi - zi)和(zi - xi)，结果就能够求出来了。算法复杂度O(n * logn)。
【题目总结】
这是一道不错的题目，首先考察了公式的变形，需要改写max - min操作，之后的等价变换和排序的思想都非常值得借鉴。
题目代码：
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 200010;
int x[N], y[N], z[N];
int main()
{
int n, a, b, c;
while (scanf("%d", &n) == 1 && n)
{
for (int i = 0; i < n; i++)
{
scanf("%d %d %d", &a, &b, &c);
x[i] = a - b;
y[i] = b - c;
z[i] = c - a;
}
sort(x, x + n);
sort(y, y + n);
sort(z, z + n);
long long ans = 0;
for (int i = 0; i < n; i++)
ans += (2 * i + 1 - n) * (long long)(x[i] + y[i] + z[i]);
printf("%I64d\n", ans / 2);
}
return 0;
}
posted on 2009-07-14 10:34
sdfond 阅读(292)
评论(0) 编辑 收藏 引用 所属分类:
Algorithm - Ad Hoc