本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2022-04-11 14:41:46

【题目链接】

题意：

给你 $n$ 堆石子，每次选三个数 $(i,j,k)$ 要求 $a_j \le 2$。

然后我们对 $(a_i , a_j , a_k)$ 进行一些操作：

$\left\{\begin{matrix} & a_j - 2\ & a_i + 1\ & a_k + 1 \end{matrix}\right.$

最后求让所有石子都在两边的最少操作次数，若无解，输出 $-1$。

题解思路：

我们先看看什么时候无解：

第一种无解的情况就是一共有 $3$ 堆，中间一堆还是奇数，那么我们只能选 $(1,2,3)$，那么只能从中间往左右分，中间怎么分总会剩一个，那么无解。

还有一种类似的情况： $(a，0，0，0，0，....，b，0，0，0，...，c)$，其中 $b$ 是奇数。 那么我们就可以把零都去掉，就变成了上一种情况，那么依旧无解。

还有一种就是所有的数都 $<2$，那么必定无解，输出 $-1$。

我们发现如果一个序列他有一个奇数，那么我们就要把一个数加到这个数上，比如： $(2,a,3,b,100)$ 此时，$3$ 是奇数，如果不给 $3$ 一个，那么 $3$ 怎么分也分不完。

就是若这个奇数前面多出来了 $2$，那么：

$(first , 2 , odd)$，我们让 $2$ 分出一个给第一个 $(first)$，另一个给这个奇数 $(odd)$，即 $odd + 1$，那么奇数的下一个就是偶数，那么这个奇数就变成了偶数。

若这个奇数的后面多出来了个 $2$，那么：

$(odd , 2 , last)$，我们让 $2$ 分出一个给最后一个 $(end)$，另一个给这个奇数 $(odd)$，那么这个奇数同样也可以变成偶数。

所以只要某个地方(当然不能是这个奇数的位置)多出来了一个 $2$，那么奇数的个数就 $-1$。

所以当一个奇数被填补之后，他就变成了一个偶数，他也能填补别的石子。

因为他被填补之后，他至少是 $2$ (因为他 $+1$ 了，所以不可能是 $0$ )，那么他就能继续填补别的奇数。

怎样证明他移动的次数是最少的呢？

对一个序列比如：

$(0 , 5 , 6 , 5 , 7)$，按照我们刚才的填法，那么对于每个奇数 $(第一个数以及最后一个数除外)$，最多会被填补一次。

因为他被填补成偶数时只会填补别的石子，而不再被填补，因为他本身就是偶数了。

那么操作成功的必要条件就是对于每个数 $a_i$，至少有一个 $\le 2$ 的。

当然若这个序列的长度为 $3$ 并且中间那个数是奇数的话，那么他 $\le 2$ 也没有用了。

【AC 记录】

AC Code:

#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1000010;
int n;
long long a[N];
int main() {
	int T;
	cin >> T;
	while (T --) {
		cin >> n;
		for (int i = 1; i <= n; ++ i)
			cin >> a[i];
		int cnt1 = 0 , cnt0 = 0 , cnte = 0;\/\/cnt1是1的个数，用来判断是否无解
		\/\/cnt0是奇数的个数，cnte是偶数的个数，当然偶数不能为0，因为如果为零那么就不能填补
		for (int i = 2; i <= n - 1; ++ i) {\/\/第一个数和最后一个数不用动，所以从2开始，到n-1
			\/\/分别统计1，奇数，偶数不包含零的个数
			if (a[i] == 1)cnt1 ++;
			else if (a[i] % 2 == 0 && a[i] != 0) cnte ++;
			else if (a[i] % 2 == 1) cnt0 ++;
		}
		bool flag = (cnte) || ((cnt0) && (cnt0 + cnt1 >= 2));\/\/判断是否有解
		if (!flag) {
			puts("-1");\/\/若无解，输出-1
			continue;
		}
		long long ans = 0;
		for (int i = 2; i <= n - 1; ++ i) ans += (a[i] + 1) \/ 2;\/\/统计步数
		cout << ans << endl;
	}	
	return 0;
}