简易题解
题目大意
给定一个包含 \(n\) 个互不相同的正整数的集合。我们需要找出这个集合中有多少个数字,恰好等于集合中另外两个不同数字的和。
思路分析
题目要求我们找出满足 A = B + C
形式的数字 A
,其中 A
, B
, C
都是给定集合中的数字,并且 B
和 C
必须是不同的数字。
由于 \(n\) 的范围较小(\(3 \le n \le 100\)),且集合中的正整数大小不超过 \(10,000\),我们可以采用比较直接的暴力枚举方法来解决。
具体步骤如下:
-
存储和快速查找: 为了方便查找一个数是否存在于集合中,我们可以使用一个布尔数组(或者整型数组作为布尔标记)来标记集合中的所有数。由于数的大小不超过 \(10,000\),我们可以创建一个大小约 \(10,001\) 的布尔数组
exists
,将exists[x]
设为true
(或1
)表示数x
存在于集合中。- 在读取输入的 \(n\) 个正整数时,将它们存入一个数组
a
的同时,也将exists[a[i]]
标记为true
。
- 在读取输入的 \(n\) 个正整数时,将它们存入一个数组
-
枚举所有可能的和: 遍历集合中所有的数字对
(a[i], a[j])
,计算它们的和sum = a[i] + a[j]
。- 为了确保
B
和C
是不同的数,我们让外层循环变量i
从 \(1\) 到 \(n\),内层循环变量j
从i+1
到 \(n\)。这样可以保证a[i]
和a[j]
总是集合中两个不同的数,并且不会重复计算a[i]+a[j]
和a[j]+a[i]
。
- 为了确保
-
检查和是否在集合中: 对于计算出的每一个和
sum
:- 检查
exists[sum]
是否为true
。如果为true
,则说明sum
这个数字也存在于原始集合中。 - 此时,
sum
就是一个满足条件的数字。
- 检查
-
去重统计: 题目要求的是“有多少个数,恰好等于集合中另外两个(不同的)数之和”。这意味着如果同一个数
X
可以通过不同的组合(B1+C1)
和(B2+C2)
得到,它也只算作一个满足条件的数。- 为了避免重复统计同一个满足条件的和,当我们发现
sum
满足条件时,应该立即将其从exists
标记中去除(例如,将exists[sum]
设为false
或0
),这样即使后面有其他组合也得到了sum
,也不会再次增加计数器。 - 每次找到一个满足条件的
sum
并且它还未被统计过时,就将计数器ans
加 \(1\)。
- 为了避免重复统计同一个满足条件的和,当我们发现
示例说明
输入:
4
1 2 3 4
- 初始化:
a = [?, 1, 2, 3, 4]
(这里数组从1开始),b
数组标记b[1]=1, b[2]=1, b[3]=1, b[4]=1
。 - 枚举:
i=1, j=2
:a[1]=1, a[2]=2
.sum = 1+2 = 3
.b[3]
是1
。ans
加 \(1\) 变为1
。并将b[3]
设为0
(防止重复统计)。i=1, j=3
:a[1]=1, a[3]=3
.sum = 1+3 = 4
.b[4]
是1
。ans
加 \(1\) 变为2
。并将b[4]
设为0
。i=1, j=4
:a[1]=1, a[4]=4
.sum = 1+4 = 5
.b[5]
是0
。不满足。i=2, j=3
:a[2]=2, a[3]=3
.sum = 2+3 = 5
.b[5]
是0
。不满足。i=2, j=4
:a[2]=2, a[4]=4
.sum = 2+4 = 6
.b[6]
是0
。不满足。i=3, j=4
:a[3]=3, a[4]=4
.sum = 3+4 = 7
.b[7]
是0
。不满足。
最终答案 ans = 2
。
代码注释
#include<bits/stdc++.h> // 包含所有标准库,方便快速编程
using namespace std; // 使用标准命名空间int a[105]; // 定义一个大小为105的整型数组a,用于存储输入的n个正整数。// 题目中n最大为100,所以105足够。
int b[20005]; // 定义一个大小为20005的整型数组b。// b[x] = 1 表示数字x在原始集合中出现过,b[x] = 0 表示未出现或已被统计。// 集合中的正整数最大10000,两数之和最大约20000 (9999+9998),所以20005足够。int main()
{int n; // 定义整型变量n,表示输入的正整数个数。cin>>n; // 从标准输入读取n的值。// 读取n个正整数,并将其存储在数组a中,同时在数组b中标记它们的存在。for(int i=1;i<=n;i++) // 循环n次,从a[1]到a[n]存储。{cin>>a[i]; // 读取第i个正整数。b[a[i]]=1; // 将数组b中对应a[i]的索引位置设为1,表示a[i]这个数存在于集合中。}int ans=0; // 定义一个整型变量ans,用于存储最终的答案(满足条件的数的个数),初始化为0。// 外层循环,枚举第一个加数a[i]for(int i=1;i<=n;i++) {// 内层循环,枚举第二个加数a[j]。j从i+1开始,保证a[i]和a[j]是集合中不同的两个数,// 且避免重复计算a[i]+a[j]和a[j]+a[i]。for(int j=i+1;j<=n;j++) {// 检查它们的和 a[i]+a[j] 是否在原始集合中,并且该和还没有被统计过。// b[a[i]+a[j]] == 1 表示和存在于集合中且未被计入答案。if(b[a[i]+a[j]]==1) {ans++; // 如果满足条件,则答案加1。b[a[i]+a[j]]=0; // 将这个和在b数组中的标记设为0,表示它已经被统计过了,防止重复计数。}}}cout<<ans<<endl; // 输出最终的答案。return 0; // 程序正常结束。
}