Moo Volume

알고리즘 문제 풀기 시작!!

문제: http://poj.org/problem?id=2231

번역: http://ckdsswprogramming.tistory.com/45

Hint

INPUT DETAILS: 

There are five cows at locations 1, 5, 3, 2, and 4. 

OUTPUT DETAILS: 

Cow at 1 contributes 1+2+3+4=10, cow at 5 contributes 4+3+2+1=10, cow at 3 contributes 2+1+1+2=6, cow at 2 contributes 1+1+2+3=7, and cow at 4 contributes 3+2+1+1=7. The total volume is (10+10+6+7+7) = 40.

cow

cow

cow

cow

cow

1번째 cow: 1+2+3+4

2번째 cow: 1+1+2+3

3번째 cow: 2+1+1+2

4번째 cow: 3+2+1+1

5번째 cow: 4+3+2+1

전부 더하면 10+7+6+7+10 = 40

---

ing...

/*

Moo Volume

Time Limit: 1000MS  Memory Limit: 65536K 

Total Submissions: 16646  Accepted: 4838 

Description

Farmer John has received a noise complaint from his neighbor, Farmer Bob, stating that his cows are making too much noise.

FJ's N cows (1 <= N <= 10,000) all graze at various locations on a long one-dimensional pasture.

The cows are very chatty animals.

Every pair of cows simultaneously carries on a conversation (so every cow is simultaneously MOOing at all of the N-1 other cows).

When cow i MOOs at cow j, the volume of this MOO must be equal to the distance between i and j, in order for j to be able to hear the MOO at all.

Please help FJ compute the total volume of sound being generated by all N*(N-1) simultaneous MOOing sessions.

Input

* Line 1: N 

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

Output

There are five cows at locations 1, 5, 3, 2, and 4.

Sample Input

5

1

5

3

2

4

Sample Output

40

Hint

INPUT DETAILS: 

There are five cows at locations 1, 5, 3, 2, and 4. 

OUTPUT DETAILS: 

Cow at 1 contributes 1+2+3+4=10, cow at 5 contributes 4+3+2+1=10, cow at 3 contributes 2+1+1+2=6, cow at 2 contributes 1+1+2+3=7, and cow at 4 contributes 3+2+1+1=7. The total volume is (10+10+6+7+7) = 40.

Source

USACO 2005 January Silver

*/

#include <stdio.h>

#include <stdlib.h>

//#include <string.h>

//#include <math.h>

#define SWAP(x, y, t) ( (t) = (x), (x) = (y), (y) = (t) )

/*

int partition(int list[], int left, int right)

{

int pivot, temp;

int low, high;

low = left;

high = right + 1;

pivot = list[left];

do{

do

low++;

while(list[low] < pivot);

do

high--;

while(list[high] > pivot);

if(low < high) SWAP(list[low], list[high], temp);

}while(low < high);

SWAP(list[left], list[high], temp);

return high;

}

void QuickSort(int list[], int left, int right)

{

if(left < right)

{

int q = partition(list, left, right);

QuickSort(list, left, q - 1);

QuickSort(list, q + 1, right);

}

}

*/

void bubbleSort(int key[], int len)

{

int tmp = 0;

int c = 0;

for(int i = len-1 ; i > -1 ; i-- )

{

for(int j = 1 ; j < i+1 ; j++)

{

if( key[j-1] > key[j] )

{

SWAP(key[j-1], key[j], tmp);

}

}

}

}

#define TESTCODE 0

int main()

{

int list[10000] = {0,};

int N = 0; //(1 <= N <= 10000)

//int N_p1 = 0;

int N_m1 = 0;

unsigned long long int sum = 0;

int tmp = 0;

#if TESTCODE

N = 10000;

#else

scanf("%d",&N); //(range 0 .. 1000000000)

#endif

//N_p1 = N+1;

N_m1 = N-1;

for (int i = 0 ; i < N ; ++i)

{

#if TESTCODE

list[i] = 1000000000 - i*13;

#else

scanf("%d",&list[i]);

#endif

}

//QuickSort(list, 0, N-1);

bubbleSort(list, N);

/*

for (int i = 0 ; i < N_m1 ; ++i)

{

sum += ( (N_m1-i)*(list[N_m1-i] - list[i]) );

//sum += total - list[i] * N;

//total -= list[i];

}

*/

for (int i = 0 ; i < N ; ++i)

{

sum += ( (N-i)*(list[N_m1-i] - list[i]) );

}

printf("%llu\n", sum<<1);

return 0;

}