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

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

【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
using namespace std;
int main()
{
int n,s=0;
cin>>n;
int a[100];
for(int i=0;i
{
cin>>a[i];
}
for(int i=0;i
{
for(int b=i+1;b
{
for(int c=0;c
{
if(i==c) continue;
if(b==c) continue;
if(a[i]+a[b]==a[c]) s++;
}
}
}
cout<
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

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

无脑暴力

我想要达到的结果

解决问题


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

第一步先按数字大小排序
然后再遍历
乱序遍历很容易出错的
排序后，你只应该检测i+b是否等于b以上的数字，不可能比b还要小


#include <stdio.h>
#include <stdlib.h>
#include <iostream>
using namespace std;
int main()
{
    int i, j, k, n, b, m;
    int a[1000];
    scanf("%d", &n);    //输入数据个数
    for(i=0; i<n; i++)  //循环输入正整数值
    {
        scanf("%d", &a[i]);
    }
    b = 0;
    for(i=0; i<n-1; i++)   //循环把数组中整数排序，冒泡排序
    {
        for(j=i+1; j<n; j++)
        {
            if(a[i] > a[j])
            {
                b = a[i];
                a[i] = a[j];
                a[j] = b;
            }
        }
    }
    m = 0;
    /*a[i]中数据以排序，故两个数之和等于a[i]的两个数必在第i个数a[i]之前
    把a[i]第二个数之前的数据逐个相加直到符合条件*/

    for(i=2; i<n; i++)  //一层循环，从第2个数据开始遍历a[i]
    {
        for(j=0; j<i-1; j++)    //二层循环，控制j从第0个数据开始到i-1遍历a[i]
        {
            for(k=j+1; k<i; k++)    //三层循环，从k=j+1开始遍历到i
            {
                if(a[j]+a[k] == a[i])   //比较如果i前有两个不同数据之和等于a[i]则m+1
                {
                    m++;
                    goto skip;  //如果有一个符合条件的就用goto跳出多重循环，不用再比较其余的啦
                }
            }
        }
skip: ;
    }
    printf("%d\n", m);
    //system("pause");
    return 0;
}

可以参考一下。
结果如图：

img