https://codeforces.com/contest/1541/problem/C
시간 2초, 메모리 256MB
input :
- t (1 ≤ t ≤ 104)
- n (1 ≤ n ≤ 105)
- d1, d2, ..., dn(1 <= di <= 109)
output :
- For each test case, output the minimum possible cost of a farm that is consistent with Farmer John's memory.
각 테스트케이스에서 John의 기억을 통해 만들 수 있는 가장 작은 비용을 출력하시오.
조건 :
-
Farmer John has a farm that consists of n pastures connected by one-directional roads.
John은 한 개의 길로 연결되어 있는 n개의 농지를 가지고 있습니다. -
Farmer John guarantees that it is impossible for the cows to get stuck in a time loop, where they can infinitely go back in time by traveling across a sequence of roads
음수로 이루어진 사이클은 없다고 합니다. -
Also, each pair of pastures is connected by at most one road in each direction.
거기에 농지들끼리 봤을 때 방향에 따라 최대 한 개의 도로로 연결되어 있습니다. -
Farmer John lost the map of the farm. All he remembers is an array d, where di is the smallest amount of time it took the cows to reach the i-th pasture from pasture 1 using a sequence of roads
John이 지도를 잃어버려 기억하고 있는 것은 배열 d 뿐입니다. 1에서 i번째 농지로 이동하는 데 걸리는 가장 작은 시간이 저장되어 씨는 배열입니다. -
The cost of his farm is the sum of the weights of each of the roads
농지에 대한 비용이라 함은 모든 도로의 가중치의 합입니다.
보면 맨 처음 d배열에 대해서 연속된 도로의 가중치로 나타낸 것이다.
그래서 가장 큰 도로를 통해 만들지 않고 한 개 한개 자잘하게 만들었다.
그런데 농지들끼리는 최대 1개의 도로로 연결되어 있다고 하니까 방향에 따라서 가는 거 오는 거가 존재할 거다.
갈 때는 여러 개의 도로를 연속적으로 사용해서 갔지만 돌아오는 경우에는 한 번에 올 수도 있다는 걸 문제 예제를 보고 알아야 할 것 같다.
그리고 입력을 받을 때에 배열이 오름차순으로 들어오는 게 아니기 때문에 가장 먼저 정렬 부터 해야 한다.
그러고 나서 가장 큰 놈을 찾는 다면 그것이 양수로 이루어진 도로의 합이 된다. 모든 가중치의 합이다.
그러면 인제 생각할 것은 음수로 된 도로를 어떻게 찾는 것인가? 이다.
만약 0 2 3 4 6 이 들어왔다고 볼 때
0 2 에다가 -2가 생길 수 있고
0 2 3 에다가 -1 -3이 생기고
0 2 3 4 에다가 -1 -2 -4가 생길 수 있다....
현재 자기 자신의 거리까지에다가 이전에 나온 값들 만큼 뺀 값이 음의 도로로 건설 되는 것이다.
그럼 이 값들을 우리는 누적합을 통해 계산을 할 수 있을 것이고 이 전까지의 농지의 개수를 통해서 몇 개나 돌아가는 길이 생길 지 알 수 있다.
import sys
for _ in range(int(sys.stdin.readline())):
n = int(sys.stdin.readline())
data = [0] + list(map(int, sys.stdin.readline().split()))
temp = [0] * (n + 1)
data.sort()
for i in range(1, n + 1):
temp[i] = temp[i - 1] + data[i]
ans = data[-1]
for i in range(1, n + 1):
ans -= data[i] * (i - 1) - temp[i - 1]
print(ans)
