P2141 珠心算测验

·标签NOIp普及组2014

·难度普及-

·时空限制1000ms / 128MB

题目描述

珠心算是一种通过在脑中模拟算盘变化来完成快速运算的一种计算技术。珠心算训练，既能够开发智力，又能够为日常生活带来很多便利，因而在很多学校得到普及。

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

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

(本题目为2014NOIP普及T1)

输入输出格式

输入格式：

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

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

输出格式：

一个整数，表示测验题答案。

输入输出样例

输入样例#1： 复制

输出样例#1： 复制

说明

【样例说明】

由 1+2=3,1+3=4 ，故满足测试要求的答案为 2 。

注意，加数和被加数必须是集合中的两个不同的数。

【数据说明】

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

【思路】

在数据数组之外再设定一个得数数组，利用得数数组与原数组各数的比较确定答案，要注意的是“其中有多少个数，恰好等于集合中另外两个（不同的）数之和？

”，有可能存在不同的两个数之和相同的情况，这时候要去重，用桶排就可以了。

【代码】

#include《iostream》

#include《cstdio》

#include《cstring》

int a[110],b[110],c[10000];

using namespace std;

int main()

{

       int n,tot=0,max=0;

       memset(b,0,sizeof(b));

       memset(c,0,sizeof(c));

       cin>>n;

       for(int i=1;i<=n;i++) cin>>a[i] ;

       for(int i=1;i<=n-1;i++)

         for(int j=i+1;j<=n;j++)

         {

            b[j]=a[i]+a[j];    //数组b中放得数

            for(int k=1;k<=n;k++)

              { if(b[j]==a[k])  c[a[k]]=1;  //数组c桶排去重

                if(a[k]>max) max=a[k];

                 }

         }

        for(int i=1;i<=max;i++)

           if (c[i]!=0) tot++;

        cout<<tot;  

        return 0;

}