【題目大意】
定義兩個三元組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 閱讀(296)
評論(0) 編輯 收藏 引用 所屬分類:
Algorithm - Ad Hoc