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

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

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

题目要求

题目背景

NOIP2014 普及 T1

题目描述

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

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

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

输入格式

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

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

输出格式

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

输入输出样例 #1

输入 #1

4
1 2 3 4

输出 #1

2

说明/提示

【样例说明】

由 $1+2=3,1+3=4$，故满足测试要求的答案为 $2$。

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

【数据说明】

对于 $100\%$ 的数据，$3 \leq n \leq 100$，测验题给出的正整数大小不超过 $10,000$。

---

题目分析

解题思路

本题的解题思路如下：

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. 复杂度分析：
   • 时间复杂度：$O(n^2)$，其中n为数组长度
   • 空间复杂度：$O(M)$，其中M为数据范围上限（10000）

---

示例代码

#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;
}               

---

所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code

GESP各级别考纲要点、知识拓展和练习题目清单详见C++学习项目主页

“luogu-”系列题目已加入洛谷Java、C++初学团队，作业清单，可在线评测，团队名额有限，欢迎加入。

“bcqm-”系列题目可在编程启蒙题库进行在线评测。