首页 > 代码库 > poj3244(公式题)

poj3244(公式题)

2024-07-26 14:46:57   220人阅读

Difference between Triplets
Time Limit: 3000MS Memory Limit: 65536K
Total Submissions: 2476 Accepted: 800

Description

For every pair of triplets, Ta = (Ia, Ja, Ka) and Tb = (Ib, Jb, Kb), we define the difference value between Ta and Tb as follows:

D(Ta, Tb) = max {Ia ? Ib, Ja ? Jb, Ka ? Kb} ? min {Ia ? Ib, Ja ? Jb, Ka ? Kb}

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 T1, T2, ... , TN. 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. 

Output

For each case, output a line with the sum of difference values between every unordered pair of triplets.

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(T1,T2)=4 
Case 2: D(T1,T2)+D(T1,T3)+D(T2,T3)=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 [-106,106]. 
The size of the input will not exceed 5 MB. 

Source

POJ Monthly--2007.07.08, Yuan, Xinhao

题目的意思非常容易理解，我就不多说了。

用n^2算法必跪的啦，必须要O(n)

先要理解max{a,b,c}-min{a,b,c}=(|a-b|+|b-c|+|c-a|)/2

假设a>b>c,那么max{a-b-c}-min{a-b-c}=a-c

而(|a-b|+|b-c|+|c-a|)/2=(a-b+b-c+c-a)/2=a-c=max{a-b-c}-min{a-b-c}

而由位置的对称性，无论a,b,c关系如何，我们总可以交换其似的a‘,b‘,c‘保持a‘>b‘>c‘,同时结果总是一致。

而| (Ia-ka) -(Ib-kb)| = |(Ia-Ib)-(ka-kb)|

所以我们对于Ti=(Ia,Ib,Ic)可以先计算Ia-Ib,Ib-Ic,Ic-Ia

这样我们要计算D(Ti,Tj),则是求(|a-b|+|b-c|+|c-a|)/2.可以保持线性。只要保证a>b, b>c, c>a,则可以将绝对值去掉。

进行排序，排序后a[i],b[i],c[i],a[i]做头的是i次，被减的是n-i-1次(从0起的坐标)

这样，ans=sum(i*(a[i]+b[i]+c[i])-(n-i-1)*(a[i]+b[i]+c[i]))

详细见代码。思路的确比较坑。


#include <iostream>
#include <algorithm>
using namespace std;
#define N 200005
long long a[N],b[N],c[N];
int main()
{
    int i,n;
    long long x,y,z;
    cin.sync_with_stdio(false);
    while(cin>>n,n){

            for(i=0;i<n;i++){
                cin>>x>>y>>z;
    a[i]=x-y,b[i]=y-z,c[i]=z-x;


            }
            sort(a,a+n);
            sort(b,b+n);
            sort(c,c+n);
            long long ans=0LL;
            for(i=0;i<n;i++){
                ans+=(i*(a[i]+b[i]+c[i])-(n-i-1)*(a[i]+b[i]+c[i]));
            }
            cout<<ans/2<<endl;

    }
    return 0;
}


poj3244(公式题)


联系
我们