C. Challenging Cliffs #726 Div.2

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

input :

• t (1≤t≤100)
• n (2≤n≤2⋅10^5)
• h1,…,hn (1≤hi≤10^9)

output :

• For each test case, output n integers — the given heights in an order that maximizes the difficulty score among all orders that minimize |h1−hn|.
• 각 테스트케이스에서 n개의 정수를 출력하시오. (난이도는 최대로, h1과 hn의 차이는 최소화 된 정답)
• 여러 답이 존재한다면, 아무거나 출력하시오.

조건 :

• you want to make the game difficult, and since walking uphill or flat is harder than walking downhill, the difficulty of the level will be the number of mountains i (1≤i<n) such that hi≤hi+1 where hi is the height of the i-th mountain.
• 게임을 어렵게 만들고 싶은데.. uphill이나 flat을 걷는 것이 downhill을 가는 것보다 어렵다. 게임의 난이도는 hi ≤ hi+1와 같은 상황의 개수가 난이도를 나타낸다.

---

우선적으로 차이가 가장 적은 두 산을 찾아야 한다. 이걸 찾을 때에도 정렬을 하고 인접한 두 산을 비교하도록 하면 찾기에 편하다.
차이가 가장 작은 두 산이지 동일한 산을 찾는 것이 아니다. 이 점을 유의하도록 하자.

그러면 찾은 산을 가지고 난이도를 어떻게 하면 가장 크게 얻을 수 있을 까 가장 차이가 적은 두 산 중에 큰 산을 제일 앞에 세우게 하고 남은 나머지를 뒤에 세운다.
그리고 나서 제일 앞에서 부터 다시 세우게 하면 이 경우 우리는 가장 높은 난이도를 얻을 수 있다.
오름차순 정렬을 한다는 것 자체가 가장 높은 난이도를 만들어 놓은 것이고 차이를 최소화 시켰기 때문에 성립하게 된다.

예외가 하나 존재하는데 산이 2개밖에 없다면 정렬 된 것을 그대로 출력해야 한다.
그렇지 않을 경우에는 downhill이 만들어져서 있던 난이도가 사라진다.

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()
    if len(data) < 3:
        print(f"{data[0]} {data[1]}")
        continue

    diff = data[1] - data[0]
    idx = 1

    for j in range(2, len(data)):
        if diff > data[j] - data[j - 1]:
            idx = j
            diff = data[j] - data[j - 1]

    for j in range(idx, len(data)):
        print(data[j], end=" ")
    for j in range(idx):
        print(data[j], end=" ")
    print()