https://codeforces.com/contest/1541/problem/A
시간 1초, 메모리 256MB
input :
- t (1 ≤ t ≤ 100)
- n (1 ≤ n ≤ 100)
output :
- Output t answers, one for each test case. Each answer consists of n integers — a permutation with the minimum total distance. If there are multiple answers, print any.
각 테스트 케이스에 대한 정답을 출력하시오. 최소한의 거리를 이용해 재배치한 배열을 출력하시오. 여러 개의 정답이 존재한다면 아무거나 출력하시오.
조건 :
- They are also lazy, so they want to minimize the total distance they move. Help them decide what cat should be at each location after the reordering.
고양이들은 너무 귀찮아서 최소한으로 움직이고 싶어한다. 재배치할 위치를 찾는 것을 도와주도록 하자
예제가 매우 큰 힌트이다.
홀수와 짝수일 때로 나눠서 경우를 생각할 수 있는데 짝수의 경우에는
짝 홀 짝 홀 ... 순서로 나열을 하면 최소한으로 움직이게 할 수 있다.
그러면 홀수일때도 비슷하게 해야하긴 하는데 어디에서 숫자를 빼와야 가장 적게 움직이게 할 수 있을 까
특정구간 [홀1 짝 홀2]의 구간에서 [2홀 1홀 짝]의 순서로 바꿔 준다면 최소한의 움직임을 가져갈 수 있다.
그러고 나서는 위의 짝수일 때와 동일하게 한다.
import sys
for _ in range(int(sys.stdin.readline())):
n = int(sys.stdin.readline())
ans = []
if n % 2 == 1:
ans = [3, 1, 2]
for i in range(4, n, 2):
ans.append(i + 1)
ans.append(i)
print(*ans)
continue
for i in range(1, n, 2):
ans.append(i + 1)
ans.append(i)
print(*ans)
