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

input :

• t (1 ≤ t ≤ 104)
• n (1 ≤ n ≤ 105)
• a1, a2, …, an (1 ≤ ai ≤ 105)

output :

• For each test case output the minimal number of operations needed or −1 if it is impossible to get the array to a state when no neighboring numbers have the same parity.
  각 테스트 케이스에서 교환을 하는 최소한의 횟수 혹은 -1을 출력하시오. 옆에 붙어있는 숫자와 동일한 parity를 가지고 있지 않는 배열을 만들 때.

조건 :

• 배열에서 두 원소를 교체할 수 있다.

• 두 원소라 함은 인접한 두 원소를 의미한다. |i - j| = 1

• 인접한 두 원소가 동일한 parity를 가지지 않는 배열을 만들기 위해 필요한 최소한의 교체를 찾으시오.

---

same parity라는 것은 짝수, 홀수를 의미한다.

그래서 대충 i가 짝수라면 i + 1, i - 1은 홀수 여야 하는 것이다.

배열

기본적으로 생각할 수 있는것은 입력된 배열의 구성이다. 짝수가 몇개인지 홀수는 몇개인지 보는 것이다.

이 구성 자체에 문제가 존재하면 -1을 출력해야 하는 것이다.

길이가 7일 때 3, 4로 구분이 안 된다거나 5일 때 2, 3으로 구분이 안 된다는 경우 말이다.

그러면 그 다음 해야 할 것은 위치를 옮겨 주는 것인데

연속된 배열

교환을 계속 한다는 것은 결국 [target_idx:i]까지의 배열이 존재하는 위치가 한 칸 씩 밀리고 [i]인 원소가 [target_idx]로 가는 것이다.

1 1 1 2 2 2
[0, 2, 4], [1, 3, 5] 이렇게 두 수들의 위치를 지정하고
[0, 1, 2], [3, 4, 5] 실제로 존재하는 위치를 저장한 후에 보면

1 2 1 1 2 2
맨 앞에 존재하던 2를 움직이면 그 앞에 있던 1 1은 한 칸씩 뒤로 밀린다.
그리고 이는 위의 인덱스의 차이를 눈 여겨 보면 관계가 보이는 데
[1, 3, 5][3, 4, 5]
'2'의 원소들이 있어야 되는 위치이다. 결국 3 - 1 2번의 교환
4 - 3 1번의 교환이 필요하다고 볼 수 있다.

1 6 6
이런 경우도 있다.
[0, 2], [1][0], [1, 2]

그냥 길이에 맞춰서 계산을 다하고 더 작은 값을 찾는 것이 편하다.

import sys

for _ in range(int(sys.stdin.readline())):
    n = int(sys.stdin.readline())
    data = list(map(int, sys.stdin.readline().split()))
    pos, idx = [[], []], data[0] % 2

    for i in range(n):
        pos[data[i] % 2].append(i)

    if len(pos[0]) not in [n // 2, n // 2 + 1] or len(pos[1]) not in [n // 2, n // 2 + 1]:
        print(-1)
        continue

    spot1, ans = [i for i in range(0, n, 2)], float('inf')

    for i in range(len(pos)):
        if len(pos[i]) != len(spot1):
            continue

        temp_ans = 0
        for j in range(len(pos[i])):
            temp_ans += abs(spot1[j] - pos[i][j])
        ans = min(temp_ans, ans)

    print(ans)