题意理解

有一个长度为 $n$ 的整数数组 $a$（下标从 $1$ 到 $n$）。
每次操作：选择下标 $i$，将 $a_i$ 减少 $2$，并将 $a_{(i \bmod n)+1}$ 增加 $1$。
可以执行任意次操作。
目标：所有元素变成相等的非负整数。
求最少操作次数，若不可能则输出 $-1$。

---

操作分析

• 一次操作相当于：$$a_i \to a_i - 2,\quad a_{i+1} \to a_{i+1} + 1$$
• 数组下标是环形的：$i = n$ 时 $i+1$ 是 $1$。
• 总和变化：$$(-2) + (+1) = -1$$ 所以每操作一次，总和减少 $1$。

---

最终状态分析

设最终所有数都等于 $x$（$x \ge 0$ 整数），进行了 $k$ 次操作。
初始总和 $S = \sum_{i=1}^n a_i$。
最终总和：$n x = S - k$。

所以：

$$k = S - n x$$

且 $k \ge 0 \implies n x \le S$。

目标：最小化 $k$，即最大化 $x$（因为 $S$、$n$ 固定）。

---

可行性的关键条件

设 $f[i]$ 表示从位置 $i$ 传递到 $i+1$ 的操作次数（$i$ 从 $0$ 到 $n-1$，$i=n-1$ 时传递到 $0$）。
注意：每次操作是一次“传递”，所以 $f[i]$ 就是执行了多少次从 $i$ 到 $i+1$ 的操作。

对于位置 $i$：

• 从 $i-1$ 收到 $f[i-1]$ 次增加（每次 +1）
• 向 $i+1$ 送出 $f[i]$ 次减少（每次 -2）
• 初始值是 $a[i]$

最终值：

$$a[i] + f[i-1] - 2 f[i] = x$$

这里下标模 $n$：$f[-1]$ 就是 $f[n-1]$。

---

环形递推

我们有 $n$ 个方程（$i = 0,1,\dots,n-1$）：

$$a[i] + f[i-1] - 2f[i] = x$$

整理得：

$$2f[i] = a[i] + f[i-1] - x$$ $$f[i] = \frac{a[i] + f[i-1] - x}{2}$$

其中 $f[-1] = f[n-1]$ 是环形条件。

---

求解方法

我们不知道 $x$ 和 $f[0]$，但：

$1$. 最大化 $x$：
因为 $k = S - n x$ 最小化，所以 $x$ 最大可取 $\lfloor S/n \rfloor$。
但 $x$ 必须使得存在非负整数解 $f[i]$。

$2$. 枚举 $f[0]$：
从 $i=1$ 到 $n-1$ 递推：

$$f[i] = \frac{a[i] + f[i-1] - x}{2}$$

需要满足：

• 分子 $\ge 0$
• 分子为偶数
• 结果 $f[i] \ge 0$

$3$. 环形验证：
最后检查 $i=0$ 的方程：

$$a[0] + f[n-1] - 2 f[0] = x$$

$4$. 为什么只尝试 $f[0]=0$ 或 $1$：
因为递推中每一步都需要分子为偶数，$f[0]$ 的奇偶性影响整个环。
但实际解如果存在，$f[0] \bmod 2$ 只有两种可能。枚举即可。

---

算法步骤

$1$. 计算总和 $S$。 $2$. 令 $x = \lfloor S/n \rfloor$（最大可能的目标值）。 $3$. 尝试 $f[0] = 0$ 和 $f[0] = 1$：

• 递推计算 $f[1]$ 到 $f[n-1]$
• 若某步出现负数或奇数，则失败
• 最后检查环形条件 $4$. 如果成功，总操作次数为：

$$k = S - n x$$

因为 $f[i]$ 总和正好是 $k$。 $5$. 否则输出 $-1$。

---

c++实现

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

void solve() {
    int n;
    cin >> n;
    vector<ll> a(n);
    ll sum = 0;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        sum += a[i];
    }

    // 最大化最终值 target = floor(sum / n)
    ll target = sum / n;
    
    // f[i] 表示从 i 传递到 i+1 的操作次数
    vector<ll> f(n, 0);
    bool ok = true;

    // 枚举 f[0] = 0 或 1（奇偶性）
    for (int start = 0; start <= 1; start++) {
        f[0] = start;
        ok = true;

        // 递推 f[1] 到 f[n-1]
        for (int i = 1; i < n; i++) {
            ll need = a[i] + f[i-1] - target;
            if (need < 0 || need % 2 != 0) {
                ok = false;
                break;
            }
            f[i] = need / 2;
        }

        // 检查环形条件
        if (ok && (a[0] + f[n-1] - 2 * f[0] == target)) {
            // 总操作次数 = sum(f[i])
            ll total_ops = 0;
            for (ll x : f) total_ops += x;
            cout << total_ops << "\n";
            return;
        }
    }

    // 无解
    cout << "-1\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

---

复杂度

每个测试用例 $O(n)$，总 $n$ 不超过 $2\times 10^5$，可通过。

---

举例验证

例 $3$：
$a = [2,1,2,6]$，$n=4$
$S = 11$，$x = \lfloor 11/4 \rfloor = 2$

尝试 $f[0]=0$：

• $f[1] = (1+0-2)/2 = -1/2$ 不行。

尝试 $f[0]=1$：

• $f[1] = (1+1-2)/2 = 0$
• $f[2] = (2+0-2)/2 = 0$
• $f[3] = (6+0-2)/2 = 2$

检查环形：$a[0] + f[3] - 2f[0] = 2 + 2 - 2 = 2$ ✅

总操作数 $k = 1+0+0+2 = 3$，输出 $3$，与题目一致。

---

总结

• 每次操作总和减 $1$，最终值 $x$ 越大操作次数越少。
• 最大化 $x = \lfloor S/n \rfloor$ 尝试。
• 转化为环形递推，枚举 $f[0]$ 的两种奇偶性。
• 验证非负整数解即可。