首页 > 其他分享 >POJ3244(工科数学分析)

POJ3244(工科数学分析)

时间:2023-05-31 16:32:32浏览次数:76  
标签:int sum long 三元组 数学分析 include 工科 LL POJ3244


题目:http://poj.org/problem?id=3244

 

题意:给定n个三元组

POJ3244(工科数学分析)_数组

,对于任意两个三元组,设

POJ3244(工科数学分析)_数组_02

POJ3244(工科数学分析)_#include_03

,定义:

 

POJ3244(工科数学分析)_数组_04

,求所有无序对

POJ3244(工科数学分析)_三元组_05

的和。

 

 

分析:首先我们要知道:

 

POJ3244(工科数学分析)_数组_06

 

简单分析一下这个结果是怎么得来的:

 

如果

POJ3244(工科数学分析)_数组_07

,那么:

 

POJ3244(工科数学分析)_#include_08

 

POJ3244(工科数学分析)_数组_09

 

这是一种情况,还有两种情况也是这个结果。所以结果成立。

 

那么我们分开计算三部分的和,然后除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

相关文章