【14NOIP普及组】珠心算测验

Question

问题遇到的现象和发生背景

【14NOIP普及组】珠心算测验

时间限制: 1000 ms 内存限制: 131072 KB
提交数: 9289 通过数: 3484
【题目描述】
珠心算是一种通过在脑中模拟算盘变化来完成快速运算的一种计算技术。珠心算训练，既能够开发智力，又能够为日常生活带来很多便利，因而在很多学校得到普及。

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

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

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

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

【输出】
输出共一行，包含一个整数，表示测验题答案。

【输入样例】
4
1 2 3 4
【输出样例】
2
【提示】
【样例说明】

由 1+2=3，1+3=4，故满足测试要求的答案为 2。注意，加数和被加数必须是集合中的

两个不同的数。

【数据说明】

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

问题相关代码，请勿粘贴截图

#include<bits/stdc++.h>
using namespace std;
int main()
{
int n,s=0;
cin>>n;
int a[100];
for(int i=0;i<n;i++)
{
cin>>a[i];
}
for(int i=0;i<n-1;i++)
{
for(int b=i+1;b<n;b++)
{
for(int c=0;c<n;c++)
{
if(i==c) continue;
if(b==c) continue;
if(a[i]+a[b]==a[c]) s++;
}
}
}
cout<<s<<endl;
return 0;
}

运行结果及报错内容

未通过

测试点 结果 内存 时间
测试点1 答案正确 584KB 2MS
测试点2 答案正确 576KB 1MS
测试点3 答案错误 588KB 1MS
测试点4 答案正确 592KB 1MS
测试点5 答案错误 584KB 1MS
测试点6 答案错误 572KB 2MS
测试点7 答案错误 584KB 2MS
测试点8 答案错误 576KB 2MS
测试点9 答案错误 576KB 2MS
测试点10 答案错误 580KB 3MS

我的解答思路和尝试过的方法

无脑暴力

我想要达到的结果

解决问题

Answer 1

#include<iostream>
#include<algorithm>
using namespace std;
int n,sum=0,ans=0;
int a[111],s[11111];
int main(){    
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    for(int i=0;i<n;i++){
        for(int j=i+1;j<n;j++){
            s[sum]=a[i]+a[j];
            sum++;    
        }
    }
    sort(s,s+sum);
    for(int i=0;i<sum;i++){
        for(int j=0;j<n;j++){
            if(s[i]==s[i-1]){
                continue;
            }
            else if(s[i]==a[j]){
                ans++;
            }
        }    
    }
    cout<<ans<<endl;
    return 0;
}

Answer 2

暴力是可以的，你可能题意理解错了：
可以把输进来的数两两相加，保存到数组里，再比对数据和数组是否相同，相同ans++;

设输入为

3

4 1 3

1.i=a[0],b=a[1],c=a[2]-------a+b=4+1!=3 X

2.i=a[0],b=a[2],c=a[1]-------a+b=4+3!=1 X

3.i=a[2],b=a[0],c=a[1]-------a+b=1+4!=3 X

因为如果两个加数有一个在数据末尾，i无法遍历，导致错误。

ps:建议换成我这种方法，只是双重循环，n在10000左右不会超时，而你三重循环只能在1000左右，一旦设定的n以后数据加量，超时无疑。