题解 | 数对计数

#include<bits/stdc++.h>
using namespace std;
int main(){
  //本题解来自牛客er@Nitrene，我仅探讨自己的理解，如有侵权请联系删除
    multiset<int> A;//因为要包括出现次数，所以要开多重集合
    int n,c,sum=0;
    cin>>n>>c;
    while(n--){
        int a=0;
        cin>>a;
        A.insert(a);
    }
    for(auto b:A){//定义b遍历多重集合A
        sum+=A.count(b+c);//若b+c在A内，则sum累计
    }
    cout<<sum<<endl;
    return 0;
  
  //我们来着重讲一下这个sum的累加原理
  /*我们知道，我们要求的是数据中有多少对有序数对的差等于特定值c，按照最常规
  的想法，我们会将数据输入到集合中进行自排序（从小到大），然后将数据推入数组中，
  使用嵌套循环对数组中的元素进行遍历，关键步骤实现如下
  int cnt{};

    for(int i=0;i<n;i++)
    {   
        
        for(int j=i;j<n;j++)
        {
            
            if(b[j]-b[i]==c){
                cnt++;
                
            }
        }
    }
	
	然而我们发现这样做的时间复杂度不符合要求，需要进行优化，
	于是我们注意到，倘若aj-ai=c，那么aj=ai+c（移项）
	惊讶的发现！我们想求出符合上述条件的式子的数量，只需
	求有多少个aj，它的值等于ai+c即可，而aj和ai都是在集合中的数据
	实现代码：
	for(auto b:A){
        sum+=A.count(b+c);
    }
	我们用实际例子来说明：
示例1
输入：
5 2
1 3 3 4 5
输出：
4
代码中的b就是ai，对于第一个b=1，1+2=3，移项就是3-1=2，满足条件的aj=3有2个
对于第二个b=3，同理有一个aj=5，使得aj=ai+c，
对于第三个b=3，同上，
后面就没有符合条件的数了，综上可以得出sum=4
题解完。
*/
}