GESP 题解库 / 3 级题解 / [GESP202409 三级] 平衡序列 · 第 13 / 28 题
GESP202409 三级 · B4038 · 简单

平衡序列

判断是否存在切分点 i,使前 i 个数之和等于后 n − i 个数之和。多组测试。

📊
t ≤ 100
数据组数
🔢
n, aᵢ ≤ 10000
数值范围
⚡
O(n)
每组时间
🎯
前缀和
核心算法
01
题目拆解
把题目拆成一块块,看清全貌

📝 题目原文

给定含 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,两边都必须非空

需要解决的问题

02
思维导图
整理解题思路的全貌
⚖️ 枚举分割线,比较左右和
📥 每组准备
读入 n 和序列
求总和 total
left = 0
注意多组数据要重置
🔁 枚举 i
i 从 1 到 n − 1
left 累加 aᵢ
right = total − left
相等即 Yes
✅ 早期退出
找到就输出 Yes
没有则输出 No
每组独立判断
别忘换行
⚠️ 易错点
i 取到 n(右段为空)
每组忘重置 left
每轮重新求和导致超时
n = 1 时必然 No
03
样例手算推导
把样例 3 组逐个验算

🧮 样例三组逐个验算

样例答案依次是 Yes、Yes、No。我们逐组算出总和,再一个个试分割线。

1
第 1 组:[1, 2, 3]

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 之间)

2
第 2 组:[2, 3, 1, 4]

total = 10

i = 1:left = 2,right = 8 → ❌

i = 2:left = 5,right = 5 → 相等 ✅

✅ Yes

3
第 3 组:[1, 2, 3, 4, 5]

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,所有分割线都失败

📊 逐组验算表

组序列totali = 1i = 2i = 3i = 4结论
1[1, 2, 3]61/5 ❌3/3 ✅——Yes
2[2, 3, 1, 4]102/8 ❌5/5 ✅6/4 ❌—Yes
3[1, 2, 3, 4, 5]151/14 ❌3/12 ❌6/9 ❌10/5 ❌No
🔑
一个有趣的观察:左右相等的条件是 total 能被 2 整除且存在前缀和恰好等于 total / 2。所以如果 total 是奇数,答案一定是 No——这是一个可以提前退出的剪枝。
04
解法对比
前缀和一遍扫描 vs 暴力双重循环

⚔️ 解法对比

🟢 前缀和滚动(推荐) 推荐

先求 total,再一遍遍历维护 left

  • 每组 O(n)
  • 总共 O(t × n)
  • 不需要额外数组
  • 代码 8 行
💡
为什么推荐:右段和 = total − left,不需要每次重新求和。这是"前缀和"思想最基础的应用。

🟠 双重循环暴力

对每个 i 分别求左段和、右段和

  • 每组 O(n²)
  • n = 10⁴ 时约 10⁸ 次
  • t = 100 时严重超时
  • 完全没必要
⚠️
注意:本题 n 可达 10⁴、t 可达 100,暴力法最坏 10¹⁰ 次运算,必然超时。

📈 性能对比

方案单组复杂度n = 10⁴ 运算量
前缀和O(n)约 10⁴ 次
双重循环O(n²)约 10⁸ 次(超时)
05
算法流程图
先求总和,再滚动比较
开始读入 t读入 n 和序列,求总和 total;left = 0i 从 1 到 n − 1left 累加 aᵢ;right = total − leftleft == right 吗?是 ✓输出 Yes 并跳出否 ✗继续下一个 it 组都处理完了吗?结束还有测试组 → 继续读入
← 左右滑动查看完整流程图
06
动手算一算
自己输入数据试试看

⚖️ 平衡序列判定器

输入一个正整数序列,程序会逐个试分割线并显示左右两边的和。

结果会显示在这里

点按钮开始 →

07
代码精讲
逐段拆解,彻底搞懂

💻 完整 C++ 代码

#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;
}
🔑
为什么用 long long?n ≤ 10⁴、aᵢ ≤ 10⁴,总和最大 10⁸ —— 其实 int 也放得下,但如果数据范围放大到 10⁵ 就会溢出。涉及累加的题目,用 long long 是零成本的好习惯。

📖 关键几行怎么看

代码作用为什么这样写
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²) 超时。
08
边界测试 & 易错点
把坑都踩一遍,考试不翻车

🧪 边界测试用例表

写完程序后,用这些数据自查一遍:

输入答案考察点
1
2
1 1
Yes两数相等,i = 1
1
4
2 3 1 4
Yesi = 2 时 5 = 5
1
5
1 2 3 4 5
No题面样例,所有分割线都失败
1
1
7
Non = 1 时没有合法 i(i 必须 < n)
1
3
1 1 1
Nototal = 3 是奇数,不可能平分
2
3
1 2 3
2
5 5
Yes
Yes
多组数据,考察状态重置
✅
自查清单:① i 的范围是 1 ~ n−1 吗?② left 每组重置了吗?③ 右段和用的是减法吗?

🚨 易错点清单

⚠️
忘记重置 left:多组数据时 left 必须每组重新置 0,否则第二组结果会错。
⚠️
i 取到 n:i 必须 < n,写成 i <= n 时当 i = n 会出现 left = total、right = 0,误判为不平衡或错误相等。
⚠️
每组都重新求右段和:right 用 total − left 直接算,不要写内层循环。
⚠️
total 是奇数时还继续算:可以提前输出 No,但即使不剪枝,正常枚举也不会出错。
09
复杂度分析
算算效率怎么样

📊 复杂度四宫格

时间复杂度
O(t × n)
空间复杂度
O(n)
t 最大
100
n 最大
10⁴

时间怎么算的?

空间都用在哪?

需要保存整组序列以便第二轮枚举,空间 O(n)。其实也可以读入时就把前缀和算好、边读边判,省掉数组(但要注意读完才能确定 total)。

✅ 最坏 10⁶ 次操作,瞬间完成;如果写成 O(n²) 则会超时,这是本题的考察点。

10
知识拓展
学一道题,会一类题

🔗 常用技巧小抄

// 前缀和的两种常见用法
// 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 求右段和区间和查询、子数组和问题
滚动变量只保留当前左段和降低空间复杂度
奇偶剪枝总和为奇数时直接判否平分问题、配对问题的快速判断
🌟
思考题:如果题目改成"能否分成三段等和",该怎么做?(提示:total 必须能被 3 整除,目标段和是 total / 3;一遍扫描累计,每当累到目标值就记一次数,最后看能否凑够 3 段。)