2014J-1：珠心算测验

洛谷：P2141
OJ：P4942

解题思路：

题目要求统计集合中有多少个数，恰好等于集合中另外两个不同的数之和。

步骤详解：

  1. 读取输入数据：
  • 首先读取正整数的个数 n。
  • 然后读取 n 个正整数，存储在数组 nums 中。
  • 为了方便快速查找某个数是否在集合中，使用 set 容器 numSet 存储所有的数。
  1. 遍历每个数 c，检查是否存在不同的数 a 和 b 使得 c = a + b：
  • 对于数组中的每个元素 nums[i]，将其作为 c 来检查。
  • 初始化一个标志变量 found，用于标记是否找到满足条件的 a 和 b。
  • 内层循环：遍历数组中的每个元素 nums[j]，将其作为 a 来检查。
    • 如果 i == j，说明 a 和 c 是同一个元素，跳过（因为需要不同的数）。
    • 计算 b = c - a。
    • 检查 b 是否等于 a 或 c，如果是，则跳过（需要三个不同的数）。
    • 使用 numSet 判断 b 是否在集合中存在。
    • 如果存在，说明找到了一组满足条件的 a 和 b，将 found 设为 true，并退出内层循环。
  1. 统计满足条件的数的个数：
  • 如果对于某个 c，found 为 true，说明存在不同的数 a 和 b，使得 c = a + b。
  • 将计数器 ans 加一。
  1. 输出结果：
  • 遍历完成后，输出计数器 ans 的值，即满足条件的数的个数。

示例解析：

以输入样例为例：

4
1 2 3 4
  • 集合中的数为 {1, 2, 3, 4}。
  • 检查每个数是否满足条件：
  • 对于 1：
    • 无法找到不同的数 a 和 b，使得 1 = a + b，故不计数。
  • 对于 2：
    • 同样无法找到满足条件的 a 和 b，故不计数。
  • 对于 3：
    • 存在 a = 1，b = 2，满足 3 = 1 + 2，且 a、b、c 互不相同，故计数器加一。
  • 对于 4：
    • 存在 a = 1，b = 3，满足 4 = 1 + 3，且 a、b、c 互不相同，故计数器再加一。
  • 最终答案为 2。

注意事项：

  • 不同的数：a、b、c 必须是集合中互不相同的数。
  • 效率优化：使用 set 进行快速查找，避免了在数组中遍历查找，提高了程序的运行效率。

代码实现：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
/**************************************************************** 
 * Description: 2014年第一题 珠心算测验
 * Author: Alex Li
 * Date: 2024-10-09 20:52:14
 * LastEditTime: 2024-10-09 20:52:19
****************************************************************/
#include <iostream>
#include <set>
using namespace std;

int main() {
    // 读入正整数的个数 n
    int n;
    cin >> n;
    // 定义数组存储 n 个正整数
    int nums[1000]; // 假设 n 不超过 1000
    // 使用集合来快速查找数是否存在
    set<int> numSet;
    for(int i = 0; i < n; i++) {
        cin >> nums[i];
        numSet.insert(nums[i]);
    }
    int ans = 0; // 初始化答案
    // 遍历数组中的每个数 c
    for(int i = 0; i < n; i++) {
        int c = nums[i];
        bool found = false; // 标记是否找到满足条件的 a 和 b
        // 遍历数组中的每个数 a
        for(int j = 0; j < n; j++) {
            if(i == j) continue; // 跳过相同的元素
            int a = nums[j];
            int b = c - a; // 计算 b
            if(b == a || b == c) continue; // 确保 a、b、c 互不相同
            if(numSet.find(b) != numSet.end()) {
                // 如果 b 在集合中，说明找到满足条件的 a 和 b
                found = true;
                break; // 跳出内层循环
            }
        }
        if(found) ans++; // 如果找到，答案加一
    }
    // 输出答案
    cout << ans << endl;
    return 0;
}
Previous Topic
Back to Lesson
Next Topic