题目:http://poj.org/problem?id=3244
题意:给定n个三元组,对于任意两个三元组,设和,定义:
,求所有无序对的和。
分析:首先我们要知道:
简单分析一下这个结果是怎么得来的:
如果,那么:
这是一种情况,还有两种情况也是这个结果。所以结果成立。
那么我们分开计算三部分的和,然后除2就可以了。
观察一下,比如对于长度为5的数组A[]计算就应该是:先排序,然后累加
A[1]-A[0]+A[2]-A[0]+A[3]-A[0]+A[4]-A[0]
A[2]-A[1]+A[3]-A[1]+A[4]-A[1]
A[3]-A[2]+A[4]-A[3]
A[4]-A[3]
把它们加起来就应该是:sum=(-4*A[0])+(A[1]-3*A[1])+(2*A[2]-2*A[2])+(3*A[3]-A[3])+(4*A[4])
考虑长度为n的数组A[],那么sum就应该这样计算:
for i 0 to n-1
begin
sum += (i*A[i] - (n-1-i)*A[i]);
end;
#include <iostream>
#include <string.h>
#include <algorithm>
#include <stdio.h>
using namespace std;
typedef long long LL;
const int N = 250000;
LL a[N],b[N],c[N];
int n;
void Import()
{
LL x,y,z;
for(int i=0;i<n;i++)
{
scanf("%I64d%I64d%I64d",&x,&y,&z);
a[i] = y-x;
b[i] = z-y;
c[i] = z-x;
}
sort(a,a+n);
sort(b,b+n);
sort(c,c+n);
}
void Work()
{
LL sum = 0;
for(int i=0;i<n;i++)
{
sum += i*a[i] - (n-1-i)*a[i];
sum += i*b[i] - (n-1-i)*b[i];
sum += i*c[i] - (n-1-i)*c[i];
}
printf("%I64d\n",sum>>1);
}
int main()
{
while(~scanf("%d",&n))
{
if(n==0) break;
Import();
Work();
}
return 0;
}
标签:int,sum,long,三元组,数学分析,include,工科,LL,POJ3244 From: https://blog.51cto.com/u_16146153/6388133