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

C++ 算法考级专栏

🎨 视觉封面

【GESP】C++三级练习 luogu-P2141 [NOIP 2014 普及组] 珠心算测验

📅 2025-06-22·✍️ OneCoder·计算中...·⏱️ 5 分钟

GESP C++三级练习,一维数组练习,难度★★✮☆☆。

luogu-P2141 [NOIP 2014 普及组] 珠心算测验

题目要求

题目背景

NOIP2014 普及 T1

题目描述

珠心算是一种通过在脑中模拟算盘变化来完成快速运算的一种计算技术。珠心算训练,既能够开发智力,又能够为日常生活带来很多便利,因而在很多学校得到普及。

某学校的珠心算老师采用一种快速考察珠心算加法能力的测验方法。他随机生成一个正整数集合,集合中的数各不相同,然后要求学生回答:其中有多少个数,恰好等于集合中另外两个(不同的)数之和?

最近老师出了一些测验题,请你帮忙求出答案。

输入格式

共两行,第一行包含一个整数 ,表示测试题中给出的正整数个数。

第二行有 个正整数,每两个正整数之间用一个空格隔开,表示测试题中给出的正整数。

输出格式

一个整数,表示测验题答案。

输入输出样例 #1

输入 #1

PLAINTEXT2 行
4
1 2 3 4

输出 #1

PLAINTEXT1 行
2

说明/提示

【样例说明】

由 ,故满足测试要求的答案为 。

注意,加数和被加数必须是集合中的两个不同的数。

【数据说明】

对于 的数据,,测验题给出的正整数大小不超过 。


题目分析

解题思路

本题的解题思路如下:

  1. 问题本质:

    • 在给定的n个不同的正整数中,找出有多少个数等于其他两个不同数字之和
    • 需要遍历所有可能的两数组合
    • 统计满足条件的数字个数
  2. 解题关键:

    • 核心思路 - 标记法:
      1. 使用两个数组实现标记:
        • array数组:存储输入的原始数字
        • r_array标记数组:下标对应数值,值为1表示该数存在
      2. 遍历所有可能的两数组合时,通过i从0到n-1,j从i+1到n-1避免重复
      3. 对于每个两数之和sum,直接在r_array[sum]中查找是否为1
      4. 找到符合条件的sum后,将r_array[sum]标记为0防止重复计数
  3. 复杂度分析:

    • 时间复杂度:,其中n为数组长度
    • 空间复杂度:,其中M为数据范围上限(10000)

示例代码

C++33 行
#include <iostream>

// 存储输入的数组,最大长度105
int array[105] = {0};
// 标记数组,用于记录数字是否出现过,最大长度20005
int r_array[20005] = {0};
int main() {
    // 输入数组长度
    int n;
    std::cin >> n;
    // 读入数组并标记每个数字
    for (int i = 0; i < n; i++) {
        std::cin >> array[i];
        // 将输入的数字在标记数组中标记为1
        r_array[array[i]] = 1;
    }
    // 计数器,记录满足条件的数字个数
    int count = 0;
    // 双重循环,遍历所有可能的数字对
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            // 如果两数之和在原数组中存在
            if (r_array[array[i] + array[j]]) {
                count++;
                // 将已经计数过的和标记为0,避免重复计数
                r_array[array[i] + array[j]] = 0;
            }
        }
    }
    // 输出结果
    std::cout << count;
    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 格式与直接回复
💬 还没有读者留言,快来成为第一个讨论者吧!