POJ 3244 Difference between Triplets 题解：（线段树或树状数组）或（排序 + 前缀和）

文章目录

Description
Input
Sample Input
Sample Output
Hint
Analysis
- Solutoin #1
- Solution #2
Code

坠痛苦的是，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

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 points和HDU 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_i$ 和 $C_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;
}

SkyWT / 博客 / POJ 3244 Difference between Triplets 题解：（线段树或树状数组）或（排序 + 前缀和）