BISHI12　元素方碑¶

中等通过率 35.05%python3样例通过牛客 AC

一句话

每次把 1 点能量在 a[i-1] 与 a[i+1] 之间搬运，问能否全部相等。

解题思路¶

这题考什么¶

找不变量。一次操作只在下标相差 2 的两个位置之间挪动 1 点能量，所以能量永远不会在奇数位和偶数位之间流动： 奇数位的总和与偶数位的总和是操作的不变量。反过来，i 的取值范围是 2..n-1，把这些操作排开看，奇数下标 1,3,5,... 构成一条「相邻两项可互换一点能量」的链，偶数下标 2,4,6,... 也是，链内部想怎么重新分配都能做到（每次只搬一格、从多的一端往少的一端搬，中途不会出现负数）。

一个量不变、其余完全自由，答案就等于对这两个不变量提要求：

总和能被 n 整除（记 v = sum / n），且
奇数位和 == v * 奇数位个数，偶数位和 == v * 偶数位个数

两条同时满足就是 YES。注意这两条不是「必要条件凑一凑」，而是充要的：必要性来自不变量，充分性来自链内可任意重排。

数据规模与复杂度¶

t <= 1e4 组、∑n <= 2e5。组数多、每组的行又短，必须一次性 sys.stdin.buffer.read().split() 读进全部 token 再用游标 p 推进； 1e4 次 input() 的系统调用开销在这个时限下不划算。每组 O(n)，总复杂度 O(∑n)。

坑在哪¶

n = 1 和 n = 2 时一条操作都做不了（i 要满足 2 <= i <= n-1，范围为空），但上面的公式天然覆盖了这两种退化情况：n = 1 时只有一个数，总和必然被 1 整除，恒 YES；n = 2 时要求 a1 == a2 == v，正是「两组各自达标」的直接结果，不必单独写特判；
判完 total % n 之后才能算 v，顺序反了会在 total 不整除时得到错误的 v；
a_i 高达 1e9、n 高达 2e5，总和可达 2e14，C++ 里必须开 long long； Python 的整数自动扩展，这一条不用操心，但换语言重写时要记得；
「奇数位」指题面里 1-based 的第 1、3、5……项，落到 Python 的 0-based 切片上是 a[0::2]，下标差一位就把两组算反了。

样例复核¶

{3,2,1}：总和 6、n = 3、v = 2；奇数位 3+1 = 4 = 22，偶数位 2 = 21，YES。 {2,4,2}：总和 8，8 % 3 != 0，直接 NO，与样例一致。

参考实现¶

solutions/BISHI12.py
import sys

data = sys.stdin.buffer.read().split()
p = 0
t = int(data[p]); p += 1
out = []
for _ in range(t):
    n = int(data[p]); p += 1
    a = data[p:p + n]; p += n            # 先切片拿走本组的 n 个 token，游标随之前移
    odd = sum(int(v) for v in a[0::2])   # 下标 1,3,5,...（0-based 的偶数位）
    even = sum(int(v) for v in a[1::2])  # 下标 2,4,6,...
    total = odd + even
    if total % n:                        # 平均值不是整数，怎么搬都不可能全相等
        out.append("NO")
        continue
    v = total // n                       # 目标值：全部相等时每一位的能量
    c_odd = (n + 1) // 2                 # 奇数位的个数（n 为奇数时比偶数位多一个）
    # 两个分组的和都必须恰好等于各自「应有」的份额，否则跨组差额永远补不平
    out.append("YES" if odd == v * c_odd and even == v * (n - c_odd) else "NO")
sys.stdout.write("\n".join(out) + "\n")

BISHI12 元素方碑¶