거리의 합
면접 대비시간 제한1초메모리 제한128 MB
수직선 위의 n개 점에서 모든 순서쌍의 거리 합을 정렬과 누적합을 이용해 효율적으로 계산합니다.
문제
수직선 위에 n개의 점이 있다. 각 점의 x좌표가 주어질 때, 모든 순서쌍 (i, j)에 대해 두 점 사이의 거리 |x_i - x_j|를 더한 값을 구하라.
즉, 1 <= i <= n, 1 <= j <= n인 모든 i, j에 대해 |x_i - x_j|의 합을 계산해야 한다.
입력
첫째 줄에 점의 개수 n이 주어진다. (1 <= n <= 10,000)
둘째 줄에는 x_1, x_2, ..., x_n이 공백으로 구분되어 주어진다. 각 좌표는 0 이상 1,000,000,000 이하의 정수이다.
출력
모든 순서쌍의 거리 합을 첫째 줄에 출력한다.