OneCoder Avatar
OneCodercoderli.com · 1024 篇博文
三级

C++ 算法考级专栏

🎨 视觉封面

【GESP】C++三级真题 luogu-B4038 [GESP202409 三级] 平衡序列

📅 2025-05-20·✍️ OneCoder·计算中...·⏱️ 5 分钟

GESP三级真题,一维数组相关题目,难度★★☆☆☆。

luogu-B4038 [GESP202409 三级] 平衡序列

题目要求

题目描述

小杨有一个包含 个正整数的序列 。他认为一个序列是平衡的当且仅当存在一个正整数 ()使得序列第 到第 个数字的总和等于第 到第 个数字的总和。

小杨想请你判断序列 是否是平衡的。

输入格式

本题单个测试点内包含多组测试数据。第一行是一个正整数 ,表示测试用例组数。

接下来是 组测试用例。对每组测试用例,一共两行。

第一行包含一个正整数 ,表示序列长度。
第二行包含 个正整数,代表序列 。

输出格式

对每组测试用例输出一行一个字符串。如果 是平衡的,输出 ,否则输出 。

输入输出样例 #1

输入 #1

CONSOLE7 行
3
3
1 2 3
4
2 3 1 4
5
1 2 3 4 5

输出 #1

CONSOLE3 行
Yes
Yes
No

说明/提示

样例 1 解释
  • 对第一组测试用例,令 ,有 ,因此序列是平衡的。
  • 对第二组测试用例,令 ,有 ,因此序列是平衡的。
  • 对第三组测试用例,不存在满足要求的 。
数据规模与约定

对全部的测试数据,保证 ,。


题目分析

解题思路

本题的解题思路如下:

  1. 输入处理:

    • 读取测试用例数量t
    • 对每组测试用例,读取序列长度n和n个整数
  2. 核心逻辑:

    • 遍历序列,计算前缀和
    • 对每个位置i,判断前i个数的和是否等于后面数的和
    • 前i个数的和可以直接用前缀和获得
    • 后面数的和 = 总和 - 前i个数的和
    • 如果找到一个满足条件的位置,输出"Yes"
    • 否则输出"No"

复杂度分析:

  • 时间复杂度:,只需要遍历一次序列
  • 空间复杂度:,需要存储序列和前缀和数组

示例代码

C++44 行
#include <iostream>

int main() {
    // 读取测试用例数量
    int t;
    std::cin >> t;
    // 遍历每个测试用例
    for (int i = 0; i < t; i++) {
        // 读取序列长度
        int n;
        std::cin >> n;
        // 定义数组存储序列
        int ary[n];
        // 计算序列总和
        int sum = 0;
        for (int j = 0; j < n; j++) {
            std::cin >> ary[j];
            sum += ary[j];
        }
        // 标记是否找到平衡点
        bool flag = false;
        // 左侧序列和
        int l_sum = 0;
        // 遍历每个位置,寻找平衡点
        for (int j = 0; j < n; j++) {
            l_sum += ary[j];
            // 判断左侧和是否等于右侧和
            // 右侧和 = 总和 - 左侧和
            if (l_sum == sum - l_sum) {
                flag = true;
                break;
            }
        }

        // 输出结果
        if (flag) {
            std::cout << "Yes" << std::endl;
            flag = false;
        } else {
            std::cout << "No" << std::endl;
        }
    }
    return 0;
}

看完题解去实战!OneCoder C++ 信奥远征闯关平台 (oi.coderli.com)
💡 OneCoder 资源指引

所有代码开源上传至 GitHub:yummy-code 仓库 · GESP 专题站:GESP WIKI

🤝 技术交流与答疑

欢迎加入:C++ GESP/CSP 考级答疑群(688906745) 与 Java/Python交流群(982860385),点击可直接加群。

📚

猜你想读 · 相关文章推荐

OneCoder

OneCoder

一个中年人的自留地,记录学习 C++、GESP/NOI、Java、Python 与算法架构的心得体会。本站唯一网址:coderli.com

读者讨论与留言

共 0 条讨论
邮箱必填 · 支持 Markdown 格式与直接回复
💬 还没有读者留言,快来成为第一个讨论者吧!