CF1556B Take Your Places!
题目描述
William 有一个包含 $n$ 个整数的数组 $a_1, a_2, \dots, a_n$。每次操作，他可以交换两个相邻的元素。如果 $|i-j|=1$，则 $a_i$ 和 $a_j$ 被认为是相邻的。
William 希望你计算出，为了使数组中不存在两个相邻元素具有相同奇偶性的情况，最少需要进行多少次交换。
输入格式
每组测试数据包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10^4$）。接下来是每个测试用例的描述。
每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 10^5$），表示 William 的数组的长度。
第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le 10^9$），表示 William 的数组。
保证所有测试用例中 $n$ 的总和不超过 $10^5$。
输出格式
对于每个测试用例，输出满足条件所需的最小操作次数。如果无法使数组中不存在两个相邻元素具有相同奇偶性，则输出 $-1$。
说明/提示
在第一个测试用例中，以下操作序列可以满足要求：
1. swap(2, 3)。执行操作后数组为 $[6, 1, 6]$。
在第二个测试用例中，初始数组已经没有两个相邻元素具有相同奇偶性。
在第三个测试用例中，以下操作序列可以满足要求：
1. swap(3, 4)。执行操作后数组为 $[1, 1, 2, 1, 2, 2]$。
2. swap(2, 3)。执行操作后数组为 $[1, 2, 1, 1, 2, 2]$。
3. swap(4, 5)。执行操作后数组为 $[1, 2, 1, 2, 1, 2]$。
在第四个测试用例中，无法满足要求。
在第五个测试用例中，以下操作序列可以满足要求：
1. swap(2, 3)。执行操作后数组为 $[6, 3, 2, 4, 5, 1]$。
2. swap(4, 5)。执行操作后数组为 $[6, 3, 2, 5, 4, 1]$。
由 ChatGPT 4.1 翻译