题解 | #元素方碑#

题目链接

题目描述

菲谢尔有一排 $n$ 个元素方碑，第 $i$ 个方碑的初始能量为 $a_i$ 。她可以对任意一个中间的方碑（下标 $i$ 满足 $1 < i < n$ ）施放雷元素进行能量转移。所有操作都必须保证任意时刻所有方碑的能量 $a_k$ 保持非负。菲谢尔想知道，她能否通过无限次操作，让所有方碑的能量变得完全相等。

解题思路

本题的解法关键在于通过分析题目给出的示例，反推出操作的真实性质，从而找到系统中的不变量。

揭示真实操作: 题目的文字描述具有一定的误导性。我们必须依赖第一个样例的说明来理解操作：
- 样例分析: 对于输入 {3, 2, 1}，样例说明指出，对下标 i=2 进行一次操作可以得到 {2, 2, 2}。
- 变化反推: 我们观察到 a_1 减少了1，a_2 不变，a_3 增加了1。这说明，在 i=2 处的操作，其效果是在它的邻居 a_1 和 a_3 之间转移了1点能量。
- 结论: 操作的本质是在 a_{i-1} 和 a_{i+1} 之间转移能量，而 a_i 仅作为媒介。
核心不变量: 既然能量只能在下标奇偶性相同的方碑之间传递（例如，a_1 与 a_3 都是奇数位，a_2 与 a_4 都是偶数位），我们发现了两个关键的不变量：
- 奇数位能量总和: 所有奇数下标的方碑（ $a_1, a_3, a_5, \dots$ ）的能量总和在任何操作下都保持不变。
- 偶数位能量总和: 所有偶数下标的方碑（ $a_2, a_4, a_6, \dots$ ）的能量总和也保持不变。
最终判定条件:
- 条件1 (总能量): 和之前一样，系统总能量 $\sum a_i$ 必须能被 $n$ 整除，得到目标平均值 $\text{avg}$ 。
- 条件2 (分组能量): 由于奇数位和偶数位的能量总和是独立的、不变的，那么初始状态必须已经满足最终的能量分布。
  - 初始奇数位总和 sum_odd_initial 必须等于最终奇数位总和 sum_odd_final。
  - 初始偶数位总和 sum_even_initial 必须等于最终偶数位总和 sum_even_final。
- 这可以转化为检查能量差：令 $d_i = a_i - \text{avg}$ ，我们必须满足：
  - $\sum d_i$ (对于所有奇数 $i$ ) $= 0$
  - $\sum d_i$ (对于所有偶数 $i$ ) $= 0$
- 因为所有能量差的总和 $\sum d_i$ 必然为0，所以上面两个条件是等价的，我们只需检查其中一个即可。

综上，我们只需要检查总能量是否能被 $n$ 整除，以及奇数位（或偶数位）的能量差之和是否为0。

代码

c++
java
python

#include <iostream>
#include <vector>
#include <numeric>

using namespace std;

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

    if (sum % n != 0) {
        cout << "NO" << endl;
        return;
    }

    long long avg = sum / n;
    long long odd_indices_diff_sum = 0;
    for (int i = 0; i < n; i += 2) {
        odd_indices_diff_sum += a[i] - avg;
    }

    if (odd_indices_diff_sum == 0) {
        cout << "YES" << endl;
    } else {
        cout << "NO" << endl;
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    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();
        while (t-- > 0) {
            solve(sc);
        }
    }

    private static void solve(Scanner sc) {
        int n = sc.nextInt();
        long[] a = new long[n];
        long sum = 0;
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextLong();
            sum += a[i];
        }

        if (sum % n != 0) {
            System.out.println("NO");
            return;
        }

        long avg = sum / n;
        long oddIndicesDiffSum = 0;
        for (int i = 0; i < n; i += 2) {
            oddIndicesDiffSum += a[i] - avg;
        }

        if (oddIndicesDiffSum == 0) {
            System.out.println("YES");
        } else {
            System.out.println("NO");
        }
    }
}

def solve():
    n = int(input())
    a = list(map(int, input().split()))
    
    total_sum = sum(a)
    
    if total_sum % n != 0:
        print("NO")
        return
        
    avg = total_sum // n
    
    odd_indices_diff_sum = 0
    for i in range(0, n, 2):
        odd_indices_diff_sum += a[i] - avg
        
    if odd_indices_diff_sum == 0:
        print("YES")
    else:
        print("NO")

def main():
    t = int(input())
    for _ in range(t):
        solve()

if __name__ == "__main__":
    main()

算法及复杂度

算法：不变量分析
时间复杂度： $\mathcal{O}(n)$ 。我们需要遍历数组来计算总和，再遍历一次来计算奇数位的能量差之和。
空间复杂度： $\mathcal{O}(n)$ 。需要一个数组来存储输入的 $n$ 个能量值。