$\color{red}{\texttt{Codeforces Round 858 (Div. 2)} }$

作者：

清风qwq , 2023-03-19 10:34:24 , 所有人可见 , 阅读 79

$$\texttt{Codeforces Round 858 (Div. 2)}$$

设原点为 $(0,0)$ ，由一些操作变为 $(c - a,d - b)$ 。

列出方程

$$p \cdot (1, 1) + q \cdot (-1, 0) = (c - a, d - b) \ \ \ (p,q均为非负整数)$$

$$
\left\{
\begin{aligned}
p = & d - b \\
q = & a + d - b - c \\
\end{aligned}
\right.
$$

若 $p \ge 0 $ 且 $q \ge 0$ ，则输出 $p+q$

否则输出 $-1$

记 $n$ 表示数组长度，$c_0$ 表示数组中 $0$ 的个数， $c_1$ 表示数组中 $1$ 的个数。

数组的分数不为 $0$ 当且仅当数组中有两个连续的 $0$ 。

先排好 $c_0$ 个 $0$ ，然后再这些 $0$ 中插入 $c_0 - 1$ 个非 $0$ 数，既保证数组分数为 $0$ 。

即

$$n - c_0 \ge c_0 - 1$$

$$c_0 \leq \frac{n+1}{2}$$

当 $c_0 > \frac{n+1}{2}$ 时，数组分数不可能为 $0$ ，考虑 $1$ 。

$1$ 由 $0$ 和 $1$ 组成，只要数组中没有 $1$ 或有一个非零且非一的数，则数组分数为 $1$ 。

若必须接触，则数组分数为 $2$ 。