boj problem 1340 简单题 费时很久 long long型 输入输出时 "%lld“ 是LL而不是11. 先快排 然后计算就可以

地址：http://acm.scs.bupt.cn/onlinejudge/showproblem.php?problem_id=1340

The Noisy Party Submit: 209    Accepted:50 Time Limit: 1000MS  Memory Limit: 65536K

Description

Nitaa is holding a party at his house. But unfortunately Nitaa has received a noise complaint from his neighbor, Arsenal4, stating that his friends in his room are making too much noise.

Nitaa's N friends (1 <= N <= 10,000) all sit at various locations on a long one-dimensional pasture. The friends are very chatty people. Every pair of friends simultaneously carries on a conversation (so every friend is simultaneously talking with all of the N-1 other friends). When friend i talks with friend j, the volume of this talk must be equal to the distance between i and j, in order for j to be able to hear the conversation at all. Please help Nitaa compute the total volume of sound being generated by all N*(N-1) simultaneous conversation. That is the total volume of conversation between all pairs of friends.

Input

* Line 1: N

* Lines 2..N+1: The location of each friend (in the range 0..1,000,000,000).

Output

Only one line that shows the total volume of the noise.

Sample Input

5

1

5

3

2

4

Sample Output

40

Source

#include<iostream>

#include<math.h>

using namespace std;

int quicksort(long long *a,int low,int high)

{

    long long temp;

    int mid;

    mid=(low+high)/2;

    temp=a[mid];

    a[mid]=a[low];

    a[low]=temp;

    while(low<high)

    {

        while(low<high && a[high]>temp)

         high--;

         if(low<high)

         a[low++]=a[high];

         while(low<high && a[low]<temp)

         low++;

         if(low<high)

         a[high--]=a[low];

                   }

         a[low]=temp;

         return low;

    }

void qsort(long long *a,int low,int high)

{

    int temp;

    if(low<high)

    {

      temp=quicksort(a,low,high);

      qsort(a,low,temp-1);

      qsort(a,temp+1,high);      

                }

    }

int main()

{

    long long  a[10001],b[10001];

    int N, i;

    long long sum=0;

      scanf( "%d", &N );    

    for( i=1; i<=N; i++)

       cin>>a[i];

    //scanf("%lld",a+i);

    qsort(a,1,N);

    b[1]=0;  b[2]=a[2]-a[1];

    sum=b[1]+b[2];

    for(i=3;i<=N;i++)

      {

        b[i]=(a[i]-a[i-1])*(i-1)+b[i-1];

        sum +=b [i];

      }

      sum=sum*2;

      cout<<sum<<endl;

   //  printf( "%lld/n", sum*2 );

    }