J - Opposites Attract 题解

算法 题解

题目大意

有n (1 ≤ n ≤ 10^5) 个人，每个人有一个数字Ti （-10<=Ti<=10） 如果一个人和另一个人的数字为相反数（0的相反数就是0），那么则可以匹配，现在求有多少种匹配的方法。

分析

我们还是可以通过一个大小为20的一维数组，记录有Ti数字的人的数量，除0外的都可以相反数相乘即可，0用组合数C(2,T0)计算。

代码

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
unsigned long long flag[21];
unsigned long long n,ans=0;
unsigned long long jc(unsigned long long n,unsigned long long m)
{
    unsigned long long i,ans=1;
    for(i=m+1;i<=n;i++)
    {
        ans*=i;
    }
    return ans;
}
int main(void)
{
    memset(flag,0,sizeof(flag));
    cin>>n;
    unsigned long long i;
    for(i=0;i<n;i++)
    {
        unsigned long long a;
        cin>>a;
        flag[a+10]++;
    }
    for(i=0;i<=10;i++)
    {
        if(i==10)
        {
            if(flag[10]<=1)
                continue;
            ans+=jc(flag[i],flag[i]-2)/2;
            continue;
        }
        ans+=flag[i]*flag[20-i];
    }
    cout<<ans<<endl;
    return 0;
}