A. Mean Inequality #723 Div.2

https://codeforces.com/contest/1516/problem/A
시간 1초, 메모리 256MB

input :

• t (1≤t≤1000)
• n (2≤n≤25)
• a1,a2,…,a2n (1≤ai≤109)

output :

• For each testcase, you should output 2n integers, b1,b2,…b2n, for which the conditions from the statement are satisfied.
  각 테스트 케이스에서 조건을 만족하는 2n개의 정수를 출력해야 한다.

조건 :

• You want to arrange the elements of the array in a circle such that no element is equal to the the arithmetic mean of its 2 neighbours.
  배열의 원소를 원으로 나열한다 했을 때 어떠한 원소도 이웃하는 2개의 원소들의 평균과 동일하지 않아야 한다.

코포는 수학을 좋아하는 거 같다.
맨 처음에 하려고 한 것은 오름차순으로 정렬을 한 후에 각 원소들을 비교해 가지고 조건에 부합하지 않는 원소의 경우 왼쪽에 위치하는 것과 위치를 바꾸게 하려 했다. 그러나 이렇게 하면 예외의 경우(틀린)들이 존재한다.

문제의 풀이를 보고야 이해를 했는데. 힌트로 배열을 두 파트로 나눠라고 한다. 일단 처음에는 홀수, 짝수로 나눠서 홀 짝 짝 홀 짝 짝 이렇게 놓으면 되지 않나 하면서 생각했는데 이게 숫자가 맞지 않는 경우가 생길 수 있다.

입력받는 배열의 수가 짝수개인것을 보고 큰 것과 작은 것으로 나눈다면 둘 다 동일한 수를 가지고 있게 할 수 있다.
그렇다면 이걸 인제 어떻게 나열하는지가 문제인데 작은 배열 중 가장 큰 값, 큰 배열 중 가장 작은 값을 놓고 동일한 값을 가지게 하려면 다른 원소는 작은 배열에서 가지고 와야 한다.
그러니까 평균이 동일한 경우를 만들지 않으려면 큰 작은 큰 작은 큰 작은 이런 순서로 나열하면 되는 것이다.

AMAZING..

import sys

t = int(sys.stdin.readline())
for i in range(t):
    n = int(sys.stdin.readline())
    data = list(map(int, sys.stdin.readline().split()))
    data.sort()

    left = data[:len(data) // 2]
    right = data[len(data) // 2:]
    ans = []
    for j in range(len(left)):
        ans.append(left[j])
        ans.append(right[j])
    print(*ans)