题解：P2141 [NOIP2014 普及组] 珠心算测验

wanghonghui123 · 2024-12-30 18:23:36 · 题解

思路

主要题意：统计集合中有多少个数，刚好等于另外两个不同数的和。

我们可以用桶的思想来解决。

• 先用标记数组 st 标记出每个元素 a_i。

• 接着将数组 a 逆序排序，方便后续操作。

• 随后判断 a_i-a_j 在数组 a 中是否出现过，意思就是有没有一个数加上 a_j 是否等于 a_i，还要判断相加的两个数是否不相等。如果是，计数器 cnt 就加一。

代码

#include <bits/stdc++.h>
using namespace std;
int a[105];
bool st[10005];
int main(){
    int n,cnt=0;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        st[a[i]]=true;
    }
    sort(a+1,a+1+n,greater<int>());
    for(int i=1;i<=n;i++){
        for(int j=i+1;j<=n;j++){
            if(st[a[i]-a[j]]&&2*a[j]!=a[i]){
                cnt++;
                break;
            }
        }
    }
    cout<<cnt;
    return 0;
}