| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 512 MB | 814 | 364 | 298 | 51.557% |
조별 과제를 위해서 수강생 $N$명의 사람의 조를 편성하려고 한다. 모든 사람은 정확히 한 개의 조에 속해야 한다. 원래 한 조는 $2$명으로 이루어져야 하지만, $N$이 홀수이기 때문에 단 하나의 조는 $3$명으로 이루어진다. 다른 $\frac{N-3}{2}$개의 조는 $2$명으로 이루어진다.
성공적인 조별 과제를 위해서는 화기애애한 분위기가 중요하다. 각 학생에게는 고유한 학번이 있으며, 어떤 조의 어색함은 해당 조에 속한 사람의 학번 중 최댓값과 최솟값의 차이로 계산된다.
조를 적절히 편성해서, 편성된 모든 조의 어색함의 합을 최소화하자.
첫 번째 줄에 수강생의 수 $N$이 주어진다. $(3 \le N \lt 500\,000;$ $N$은 홀수$)$
두 번째 줄에 각 학생의 학번을 의미하는 $N$개의 정수 $A_1, A_2, \cdots, A_N$이 공백으로 구분되어 주어진다. $(1 \le A_i \le 10^9)$ 주어지는 $A_i$는 서로 다르다.
조를 적절히 편성해서, 편성된 모든 조의 어색함의 합의 최솟값을 출력하여라.
5 3 1 4 5 9
7
학번이 $3, 1$인 사람을 한 조로 묶고, $4, 5, 9$인 사람을 한 조로 묶으면 각 조의 어색함은 $(3-1) = 2$와 $(9-4) = 5$이고, 합은 $7$이다.
이 방법이 각 조의 어색함의 합을 최소로 하는 방법이다.
7 20 10 9 11 3 18 1
6