BGN09 元素方碑

思路

拿到这题先别急着模拟操作，先想一个关键问题：每次操作到底改变了什么？

题目说对第 块方碑施放雷元素，正面轰击让能量从 流向 ，反面轰击让能量从 流向 。注意了， 本身是不变的——它只是一个"中转站"，能量是在它的两个邻居之间跳了一格。

能量只能隔一个位置转移

这意味着什么呢？每次操作本质上是在 和 之间移动一个单位的能量。也就是说，能量只能在间隔为2的位置之间流动。

那你再想想：位置 0 的能量可以转到位置 2（通过操作位置 1），位置 2 的能量可以转到位置 4（通过操作位置 3）……但位置 0 的能量永远不可能流到位置 1、3、5 这些奇数位。

奇偶分组

所以整个数组天然分成了两组：

  • 偶数组：
  • 奇数组：

同一组内的能量可以自由流动（通过连续的中转操作），但跨组的能量传输是不可能的。

判断条件

要让所有方碑能量都等于 ，需要满足两个条件：

  1. 总和能整除： 必须是 的倍数；
  2. 奇偶组内能量匹配：偶数组的能量之和 = 偶数组的元素个数 target（奇数组自然也满足）。

验证样例

  • ：target=2，偶数组 和=4=2×2，奇数组 和=2=1×2。YES
  • ：target=2，偶数组 和=3≠2×2=4。NO
  • ：target=2，偶数组 和=8≠3×2=6。NO

全部吻合！

代码

#include <bits/stdc++.h>
using namespace std;
int main(){
    int t;
    scanf("%d", &t);
    while(t--){
        int n;
        scanf("%d", &n);
        long long s = 0, se = 0; // s=总和, se=偶数位之和
        int ce = 0;              // ce=偶数位个数
        for(int i = 0; i < n; i++){
            long long x;
            scanf("%lld", &x);
            s += x;
            if(i % 2 == 0){
                se += x;
                ce++;
            }
        }
        if(s % n != 0){
            puts("NO");
        } else {
            long long target = s / n;
            // 偶数组能量总和 == 偶数组元素个数 * target
            puts(se == (long long)ce * target ? "YES" : "NO");
        }
    }
    return 0;
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        StringBuilder sb = new StringBuilder();
        while (t-- > 0) {
            int n = sc.nextInt();
            long s = 0, se = 0;
            int ce = 0;
            for (int i = 0; i < n; i++) {
                long x = sc.nextLong();
                s += x;
                if (i % 2 == 0) {
                    se += x;
                    ce++;
                }
            }
            if (s % n != 0) {
                sb.append("NO\n");
            } else {
                long target = s / n;
                sb.append(se == (long) ce * target ? "YES\n" : "NO\n");
            }
        }
        System.out.print(sb);
    }
}

import sys
input = sys.stdin.readline

t = int(input())
out = []
for _ in range(t):
    n = int(input())
    a = list(map(int, input().split()))
    s = sum(a)
    if s % n != 0:
        out.append("NO")
    else:
        target = s // n
        se = sum(a[i] for i in range(0, n, 2))
        ce = (n + 1) // 2
        out.append("YES" if se == ce * target else "NO")
print('\n'.join(out))

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin });
const lines = [];
rl.on('line', line => lines.push(line));
rl.on('close', () => {
    let idx = 0;
    const t = parseInt(lines[idx++]);
    const out = [];
    for (let i = 0; i < t; i++) {
        const n = parseInt(lines[idx++]);
        const a = lines[idx++].trim().split(' ').map(Number);
        let s = 0, se = 0, ce = 0;
        for (let j = 0; j < n; j++) {
            s += a[j];
            if (j % 2 === 0) {
                se += a[j];
                ce++;
            }
        }
        if (s % n !== 0) {
            out.push("NO");
        } else {
            const target = s / n;
            out.push(se === ce * target ? "YES" : "NO");
        }
    }
    console.log(out.join('\n'));
});

复杂度

  • 时间复杂度：，每个元素只遍历一次。
  • 空间复杂度：，只需要几个变量记录总和。

总结

这题的核心就一句话：操作不改变中间元素，只在左右邻居间搬运，所以能量只能在奇数位和偶数位各自内部流动。想明白这个，条件就很直白了——总和能整除 ，并且奇偶两组的能量各自够分。