平衡序列 题解

题目分析

我们需要判断一个正整数序列 $a$ 是否是“平衡的”。

平衡的定义：存在一个位置 $i$（$1\le i<n$），使得前 $i$ 个数的总和 等于 第 $i+1$ 到第 $n$ 个数的总和。也就是说，在序列的某个位置切一刀，左半部分的和与右半部分的和相等。

输入格式：多组测试数据，每组数据给出长度 $n$ 和序列 $a_1 \sim a_n$。
输出格式：对每组数据输出 Yes 或 No。

解题思路

记整个序列的总和为 $S$。
如果我们选择一个分界点 $i$，那么：

• 左半部分和为 $L = a_1 + a_2 + \dots + a_i$
• 右半部分和为 $R = a_{i+1} + \dots + a_n$

由于 $L + R = S$，要使 $L = R$，必须有 $L = R = \frac{S}{2}$。
因此问题转化为：是否存在某个位置 $i$，使得前 $i$ 个数的前缀和恰好等于总和的一半？

需要注意：

• $i$ 的取值范围是 $1\le i<n$，即不能取 $i=n$（那样右边为空，和不可能相等）。
• 如果 $S$ 是奇数，那么不可能有前缀和等于 $S/2$，可以直接判定为 No。
• 因为序列中的数都是正整数，前缀和是单调递增的，所以最多只有一个位置可能满足条件。

算法说明

我们可以采用计算前缀和并实时判断的方法：

1. 读入 $n$ 和序列，同时累加计算出总和 $S$。
2. 初始化当前前缀和 $prefix = 0$，标记 $found = \text{false}$。
3. 遍历 $i$ 从 $1$ 到 $n-1$：
   • 将 $a_i$ 加入 $prefix$。
   • 如果 $2 \times prefix == S$，说明找到了平衡点，设置 $found = \text{true}$ 并结束循环。
4. 根据 $found$ 输出 Yes 或 No。

该方法只需要一次遍历即可完成判断。

样例验证：

• 样例 1：序列 1 2 3，总和 $S=6$，$i=2$ 时前缀和为 $3$，$2 \times 3 = 6$，输出 Yes。
• 样例 2：序列 2 3 1 4，总和 $S=10$，$i=2$ 时前缀和为 $5$，$2 \times 5 = 10$，输出 Yes。
• 样例 3：序列 1 2 3 4 5，总和 $S=15$ 为奇数，不可能找到，输出 No。

时间复杂度分析

对于每组测试数据：

• 计算总和需要遍历 $n$ 个元素，时间复杂度 $O(n)$。
• 寻找平衡点需要再次遍历最多 $n-1$ 个元素，时间复杂度 $O(n)$。

整体每组时间复杂度为 $O(n)$。
共有 $t$ 组数据，总时间复杂度为 $O(\sum n)$。在题目给定的数据范围（$t \le 100$，$n \le 10000$）下可以轻松通过。

参考代码及解释

cpp
复制
1#include<bits/stdc++.h>
2using namespace std;
3
4int a[10010];  // 存储序列，题目 n ≤ 10000
5
6int main() {
7    int t;
8    cin >> t;
9    while (t--) {           // 处理每组测试数据
10        int n;
11        cin >> n;
12        int sum = 0;
13        for (int i = 1; i <= n; i++) {
14            cin >> a[i];
15            sum += a[i];   // 同时计算总和
16        }
17        int tot = 0, fl = 0;
18        // 遍历前 n-1 个元素，计算前缀和
19        for (int i = 1; i < n; i++) {
20            tot += a[i];            // 累加得到前 i 项和
21            if (tot * 2 == sum) {   // 判断是否为总和的一半
22                fl = 1;            // 找到平衡点
23                break;
24            }
25        }
26        if (fl) cout << "Yes\n";
27        else cout << "No\n";
28    }
29    return 0;
30}

代码说明：

• sum 记录整个序列的总和。
• tot 记录当前的前缀和。
• fl 作为标记，fl == 1 表示已找到平衡点。
• 遍历时只需到 $i = n-1$，因为右半部分不能为空。
• 使用 tot * 2 == sum 来避免浮点数和整除的问题，即使 $sum$ 是奇数也能正确判断（此时等式不可能成立）。
• 找到后立即 break 可以节省时间。

这道题考察了对前缀和的简单应用，只要理清“总和的一半”这个条件，代码实现就不难了。