POJ 3244 Difference between Triplets 题解:数学+(线段树或树状数组)或(排序+前缀和)

/ 0评 /

坠痛苦的是,POJ 的辣鸡 G++ 编译器不支持 long long,害得我调试调了半天……

Description

For every pair of triplets, T_a = (I_a, J_a, K_a) and T_b = (I_b, J_b, K_b), we define the difference value between T_a and T_b as follows:

D(T_a, T_b) = \max (I_a − I_b, J_a − J_b, K_a − K_b) − \min (I_a − I_b, J_a − J_b, K_a − K_b)

Now you are given N triplets, could you write a program to calculate the sum of the difference values between every unordered pair of triplets?

Input

The input consists of several test cases.
Each test case begins with a line containing an integer N, denotes the number of triplets. Assume that we number the triplets as T_1, T_2, \dots , T_N. Then, there are following N lines, each line contains three integers, giving the elements of each triplet.
A case with N = 0 indicates the end of the input.

Sample Input

2
1 2 3
3 2 1
3
1 3 2
4 0 7
2 2 9
0

Sample Output

4
20

Hint

Case 1: D(T_1,T_2)=4
Case 2: D(T_1,T_2)+D(T_1,T_3)+D(T_2,T_3)=8+8+4=20

You can assume that N, the number of triplets in each case, will not exceed 200,000 and the elements in triplets fit into [-10^6,10^6].
The size of the input will not exceed 5 MB.

Analysis

Solutoin #1

很类似上次的HDU 5626 Clarke and pointsHDU 6447 YJJ’s Salesman的结合,我们可以先分类讨论(因为这是一个轮换对称式,其实随便考虑一种情况就可以了)。

假设 \max (I_a − I_b, J_a − J_b, K_a − K_b) = I_a - I_b,那么就有:

I_a-I_b>J_a-J_b,I_a-I_b>K_a-K_b

变换得到:

I_a-J_a>I_b-J_b,I_a-K_a-i_b-K_b

A_i=I_i-J_i,B_i=I_i-K_i,显然 A_i>A_j,B_i>B_j
这就转换成区间选点问题了。只需要先按照 A_i 排序,然后用线段树或者树状数组维护下就可以了~

Solution #2

上面的解法显然太麻烦了,其实有一种更加精妙的做法。

首先我们要知道一个超级重要的公式:

\max(a,b,c)-\min(a,b,c) = \frac {|a-b|+|b-c|+|c-a|} 2

所以可以得到:

D(T_a, T_b) = \max (I_a − I_b, J_a − J_b, K_a − K_b) − \min (I_a − I_b, J_a − J_b, K_a − K_b) \\\\ = \frac {|I_a-I_b-J_a+J_b| + |J_a-J_b-K_a-K_b| + |K_a-K_b-I_a+I_b|} 2

同样令 A_i=I_i-J_i,B_i=J_i-K_i,C_i=K_i-A_i,整理得到:

D(T_a,T_b)=\frac {|A_a-A_b|+|B_a-B_b|+|C_a-C_b|} 2

所以只需要对于每个 A_i,累计它与所有小于它的 A_i 之差之和,对于 B_iC_i 同理。即:

\sum D(T_i,T_j) = \frac {\sum_{A_i< A_j} (A_j-A_i) +\sum_{C_i< C_j} (C_j-C_i) + \sum_{C_i< C_j} (C_j-C_i) } {2}

这个很好做,维护下加和就好了。

Code

第一种解法代码懒得写了……
\下面是解法二的代码。POJ 这题提交的时候如果语言选择 G++ 会 WA 掉,但是用 C++ 就过了……困扰了我很长时间……

嗯,原来在 FAQ 里面说了:

Prior to the compiler upgrade in May 2009, we serviced C and C++ submissions using GCC 3.4.2. That version of GCC relies on the old MS VC++ 6 runtime library, which does not support the %lld and %llu specifiers for signed and unsigned long long types but allows the standard-incompliant %lf and %lg specifiers for floating-point types. The new GCC 4.4.0 comes with its own ISO C-conformant implementation of the printf function. Now you can use %lld and %llu with either C/C++ compiler, but %lf and %lg only work with MS VC++ 2008 Express. As a rule of thumb, you should always use the %f and %g specifiers instead for floating-point types.

…可怕……

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const long long maxn=200005;
long long n,a[maxn],b[maxn],c[maxn];
long long ans=0;

int main(){
    for (;;){
        scanf("%lld",&n);
        if (n==0) break;
        ans=0;

        for (long long i=1;i<=n;i++){
            long long x,y,z;
            scanf("%lld%lld%lld",&x,&y,&z);
            a[i]=x-y,b[i]=y-z,c[i]=z-x;
        }
        sort(a+1,a+1+n);sort(b+1,b+1+n);sort(c+1,c+1+n);

        long long sum_a=0,sum_b=0,sum_c=0;
        for (long long i=1;i<=n;i++){
            ans+=a[i]*(i-1)-sum_a;
            ans+=b[i]*(i-1)-sum_b;
            ans+=c[i]*(i-1)-sum_c;
            sum_a+=a[i];sum_b+=b[i];sum_c+=c[i];
        }
        printf("%lld\n",ans/2);
    }
    return 0;
}

知识共享许可协议 本文章采用 知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议 进行许可。
欢迎转载,如有错误欢迎指出。
本文链接:https://skywt.cn/posts/poj3244/


发表评论

电子邮件地址不会被公开。 必填项已用*标注