- [NOIP2014 普及组] 珠心算测验
.
- @ 2026-3-17 16:35:55
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin >> n;
int num[n];
int cnt=0;
for(int i=0;i<n;i++)
{
cin >>num[i];
}
sort(num,num+n);
for (int i=n-1;i>=2;i++)
{
int temp=num[i];
int l=0,r=i-1;
int sum;
bool flag=1;
while(l<r)
{
sum=num[l]+num[r];
if(sum==temp)
{
cnt++;
flag=0;
break;
}
else if(sum>temp)
{
r--;
}
else
{
l++;
}
}
}
cout << cnt;
return 0;
}
1 comments
-
Myobot @ 2026-3-17 16:36:16
同学你好,我看了你的代码。你的思路是先将数组排序,然后对每个数(从大到小)使用双指针检查是否存在两个不同的数之和等于它。这是一个正确的思路方向,但代码中有几个关键的错误需要你自己发现并修正。
主要问题分析:
-
循环条件错误:
for (int i=n-1;i>=2;i++)这里你想从最后一个元素开始向前遍历,但循环条件是i>=2且每次i++,这会导致:- 初始
i=n-1,如果n-1 >= 2,循环会执行 - 但每次
i++会让i变大,永远不会满足i>=2的终止条件吗?实际上当i超过int最大值时会溢出,但在此之前循环会一直执行,访问非法内存。 - 你应该使用
i--而不是i++。
- 初始
-
重复计数问题:题目要求统计“有多少个数”满足条件,而不是“有多少种两数之和的组合”。你的代码中,如果某个数
temp有多种两数之和的组合(例如5 = 1+4 = 2+3),你的cnt++会被执行多次吗?实际上因为找到一组就break,所以不会重复计数,这点是对的。 -
边界条件:你从
i=n-1开始,r=i-1,l=0,这确保了三个数互���相同,符合题意。
引导思考:
- 修正循环方向后,你的算法时间复杂度是 (外层 次,内层双指针平均 )。对于 完全足够。
- 但还有一个隐藏问题:题目要求统计的是“集合中多少个数等于另外两个不同数之和”。假设数组是
[1,2,3,4,5],那么3=1+2,4=1+3,5=1+4=2+3。你的算法会正确统计出 3 个数吗? - 考虑这个例子:
[1,2,3,4,6]。3=1+2,4=1+3,但6=2+4也成立。你的算法应该能正确处理。
建议调试步骤:
- 先修正循环方向(
i--)。 - 用题目给的样例
4\n1 2 3 4测试,应该输出2。 - 再测试一些边界情况,比如:
3\n1 2 3应该输出1(只有3=1+2)。5\n1 2 3 4 5应该输出3(3,4,5)。5\n1 2 3 4 6应该输出3(3,4,6)。
代码结构提示:
你的双指针部分逻辑基本正确,但
flag变量似乎没有实际用途(你设置了但没使用)。可以考虑移除。最终挑战:
如果数组中有重复的数字怎么办?题目说“集合中的数各不相同”,所以不需要考虑重复。
请先尝试修正最明显的错误(循环方向),然后测试几个例子。如果还有问题,可以再上传修正后的代码,我会继续帮你分析。
-
- 1
Information
- ID
- 1339
- Time
- 1000ms
- Memory
- 256MiB
- Difficulty
- 7
- Tags
- # Submissions
- 155
- Accepted
- 33
- Uploaded By