判断是否存在切分点 i,使前 i 个数之和等于后 n − i 个数之和。多组测试。
给定含 n 个正整数的序列 a。如果存在正整数 i(1 ≤ i < n)使得第 1 到第 i 个数字之和等于第 i+1 到第 n 个数字之和,则称该序列是平衡的。请判断给定的序列是否平衡。
本题包含多组测试数据。
前缀和多组测试枚举分割线总和不变量
| 项目 | 说明 |
|---|---|
| 输入 | 第一行 t;每组两行:n 和 n 个数 |
| 输出 | 每组一行 Yes 或 No |
| 数据范围 | t ≤ 100,1 ≤ n, aᵢ ≤ 10000 |
| 切分限制 | 1 ≤ i < n,两边都必须非空 |
样例答案依次是 Yes、Yes、No。我们逐组算出总和,再一个个试分割线。
total = 6
i = 1:left = 1,right = 6 − 1 = 5 → 1 ≠ 5 ❌
i = 2:left = 1 + 2 = 3,right = 6 − 3 = 3 → 相等 ✅
✅ Yes(分割线在 2 与 3 之间)
total = 10
i = 1:left = 2,right = 8 → ❌
i = 2:left = 5,right = 5 → 相等 ✅
✅ Yes
total = 15
i = 1:1 vs 14 ❌
i = 2:3 vs 12 ❌
i = 3:6 vs 9 ❌
i = 4:10 vs 5 ❌
(i 最大只能到 4,因为 i < n = 5)
❌ No,所有分割线都失败
| 组 | 序列 | total | i = 1 | i = 2 | i = 3 | i = 4 | 结论 |
|---|---|---|---|---|---|---|---|
| 1 | [1, 2, 3] | 6 | 1/5 ❌ | 3/3 ✅ | — | — | Yes |
| 2 | [2, 3, 1, 4] | 10 | 2/8 ❌ | 5/5 ✅ | 6/4 ❌ | — | Yes |
| 3 | [1, 2, 3, 4, 5] | 15 | 1/14 ❌ | 3/12 ❌ | 6/9 ❌ | 10/5 ❌ | No |
先求 total,再一遍遍历维护 left
对每个 i 分别求左段和、右段和
| 方案 | 单组复杂度 | n = 10⁴ 运算量 |
|---|---|---|
| 前缀和 | O(n) | 约 10⁴ 次 |
| 双重循环 | O(n²) | 约 10⁸ 次(超时) |
输入一个正整数序列,程序会逐个试分割线并显示左右两边的和。
点按钮开始 →
#include <bits/stdc++.h> using namespace std; int main() { int t; scanf("%d", &t); while (t--) { int n; scanf("%d", &n); int a[10005]; long long total = 0; for (int i = 0; i < n; i++) { scanf("%d", &a[i]); total += a[i]; } bool ok = false; long long left = 0; for (int i = 1; i < n; i++) { // i 表示左段长度,最大 n-1 left += a[i - 1]; // 左段和滚动累加 long long right = total - left; // 右段和 = 总和 - 左段和 if (left == right) { ok = true; break; } } printf("%s\n", ok ? "Yes" : "No"); } return 0; }
| 代码 | 作用 | 为什么这样写 |
|---|---|---|
total += a[i] | 读入时求和 | 顺便完成,不用再遍历一次 |
for (i = 1; i < n; i++) | 枚举分割线 | i 是左段长度,最大只能到 n−1 |
left += a[i - 1] | 滚动更新左段和 | 每轮加上刚并入左段的那个元素 |
right = total - left | 右段和 | 用减法代替重新求和,这是关键优化 |
i <= n,会让右段为空(和为 0);② left 定义在 while 外面,下一组数据继承了上一组的和;③ 每个 i 都重新求右段和,导致 O(n²) 超时。写完程序后,用这些数据自查一遍:
| 输入 | 答案 | 考察点 |
|---|---|---|
1 | Yes | 两数相等,i = 1 |
1 | Yes | i = 2 时 5 = 5 |
1 | No | 题面样例,所有分割线都失败 |
1 | No | n = 1 时没有合法 i(i 必须 < n) |
1 | No | total = 3 是奇数,不可能平分 |
2 | Yes Yes | 多组数据,考察状态重置 |
left 必须每组重新置 0,否则第二组结果会错。i <= n 时当 i = n 会出现 left = total、right = 0,误判为不平衡或错误相等。right 用 total − left 直接算,不要写内层循环。需要保存整组序列以便第二轮枚举,空间 O(n)。其实也可以读入时就把前缀和算好、边读边判,省掉数组(但要注意读完才能确定 total)。
✅ 最坏 10⁶ 次操作,瞬间完成;如果写成 O(n²) 则会超时,这是本题的考察点。
// 前缀和的两种常见用法 // 1) 滚动维护(本题用法,O(1) 空间) long long left = 0; for (int i = 1; i < n; i++) { left += a[i - 1]; long long right = total - left; } // 2) 预先打表(多次查询区间和时更方便) long long pre[100005]; pre[0] = 0; for (int i = 1; i <= n; i++) pre[i] = pre[i - 1] + a[i - 1]; // 区间 [l, r] 的和 = pre[r+1] - pre[l] // 判断能否平分的小剪枝 if (total % 2 != 0) { printf("No\n"); continue; }
把这道题用到的基本功拆出来,它们能迁移到很多同类问题上。
| 能力点 | 本题怎么用 | 还能迁移到 |
|---|---|---|
| 前缀和 | 用 total − left 求右段和 | 区间和查询、子数组和问题 |
| 滚动变量 | 只保留当前左段和 | 降低空间复杂度 |
| 奇偶剪枝 | 总和为奇数时直接判否 | 平分问题、配对问题的快速判断 |