B. Transfusion 题解

难度：1100 | 标签：数学、不变量、思维题

题目大意

给定一个长度为 $n$ 的数组，你可以执行任意次操作： 选择下标 $i(2 \le i \le n-1)$，将 $a_{i-1}$ 和 $a_{i+1}$ 中的一个减 $1$、另一个加 $1$（操作后所有数非负）。 问：能否通过操作让数组所有元素相等？

核心观察（解题关键）

我们先分析操作的不变性质（这是思维题的核心）：

1. 数值只能跨位转移：操作仅在间隔一位的位置（$i-1 \leftrightarrow i+1$）之间转移数值，中间元素 $a_i$ 永远不会被修改；
2. 奇偶下标分组不变：
   • 所有奇数下标的元素只能和奇数下标元素交换数值；
   • 所有偶数下标的元素只能和偶数下标元素交换数值； → 奇数位总和、偶数位总和是固定不变的！
3. 总和不变：所有操作不改变数组总数值。

判定条件

要让数组所有元素相等，必须同时满足两个条件：

1. 总和可均分：数组总和 $\text{total}$ 能被长度 $n$ 整除，即 $\text{total} \% n = 0$，平均值 $\text{avg} = \text{total} / n$；
2. 奇偶分组匹配： 奇数位的总数值 = 奇数位的数量 × 平均值 偶数位的总数值 = 偶数位的数量 × 平均值

完整AC代码

#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        ll total = 0, sum_odd = 0, sum_even = 0;
        for (int i = 1; i <= n; ++i) {
            ll x;
            cin >> x;
            total += x;        // 计算数组总和
            if (i & 1) sum_odd += x;  // 奇数下标总和
            else sum_even += x;       // 偶数下标总和
        }

        // 条件1：总和必须能被n整除，否则直接无解
        if (total % n != 0) {
            cout << "NO\n";
            continue;
        }
        ll avg = total / n;
        int cnt_odd = (n + 1) / 2;  // 奇数下标数量
        int cnt_even = n / 2;       // 偶数下标数量

        // 条件2：奇偶分组总和必须匹配平均值
        if (sum_odd == 1LL * cnt_odd * avg && sum_even == 1LL * cnt_even * avg) {
            cout << "YES\n";
        } else {
            cout << "NO\n";
        }
    }
    return 0;
}

代码细节解析

1. 数据类型 使用 long long 存储总和，避免溢出（$a_i \le 10^9$，$n \le 2\times10^5$，总和可达 $2\times10^{14}$）。

2. 输入加速 ios::sync_with_stdio(false); cin.tie(nullptr); 加速大数据输入，适配 $t \le 10^4$ 的数据规模。

3. 关键计算

   • cnt_odd = (n+1)/2：奇数下标的数量；
   • cnt_even = n/2：偶数下标的数量；
   • 1LL * cnt_odd * avg：强制转为 long long，防止整数溢出。

复杂度分析

• 时间复杂度：$\boldsymbol{O(\sum n)}$ 遍历数组一次计算总和，所有测试用例的 $n$ 之和 $\le 2\times10^5$，完全满足时间限制；
• 空间复杂度：$\boldsymbol{O(1)}$ 仅使用常数变量，无额外空间开销。

样例验证（第4组测试用例）

输入：

4
1 6 6 1

计算：

• 总和 $\text{total}=14$，$n=4$，$14\%4=2 \neq 0$ → 直接输出 NO，与标准答案一致。

总结

这道题是经典的不变量思维题，不需要模拟操作，只需要抓住：

1. 总和必须可均分；
2. 奇偶下标分组的总和固定不变。 抓住这两个核心性质，代码就能轻松通过所有测试点。