洛谷-P1102 A-B 数对

原题链接

¶分析

通过分析样例发现，可能存在重复的数字，第一个1与2构成一个数对，第二个1与2也构成一个数对，1重复了2次，所以考虑用一个变量存储出现数字的次数，score+=B重复次数 * A重复次数。首先想到用结构体数组存储1~C范围中可能出现的次数，但发现C太大，数组无法存下，考虑用字典存储。

A-B=C等价于B+C=A，所以从头遍历字典a，如果存在a[b+c]，则score+=a[b] * a[b+c]

¶code

#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false)
int main()
{
    IOS;
    LL n,c,score = 0;
    int cnt;
    map<LL,LL> a;
    cin>>n>>c;
    for(int i=0;i<n;i++) {
        cin>>cnt;
        a[cnt]++;
    }
    for(auto [num,times] : a) {
        if(a.find(num+c)!=a.end())		//如果存在B+C=A
        score += a[num] * a[num+c];
    }
    cout<<score;
    return 0;
}