CF1637题解
FiraCode
·
·
题解
【题目链接】
题意：
给你 n 堆石子，每次选三个数 (i,j,k) 要求 a_j \le 2。
然后我们对 (a_i , a_j , a_k) 进行一些操作：
& a_j - 2\\
& a_i + 1\\
& a_k + 1
\end{matrix}\right.
最后求让所有石子都在两边的最少操作次数，若无解，输出 -1。
题解思路：
我们先看看什么时候无解：
第一种无解的情况就是一共有 3 堆，中间一堆还是奇数，那么我们只能选 (1,2,3)，那么只能从中间往左右分，中间怎么分总会剩一个，那么无解。
还有一种类似的情况：
那么我们就可以把零都去掉，就变成了上一种情况，那么依旧无解。
还有一种就是所有的数都 $<2$，那么必定无解，输出 $-1$。
我们发现如果一个序列他有一个奇数，那么我们就要把一个数加到这个数上，比如：
就是若这个奇数前面多出来了 $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 记录】](https://www.luogu.com.cn/record/73720257)
## AC Code:
```cpp
#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;
}
```