P1296 奶牛的耳语

· · 题解

题目传送门

简述题意：给定一个序列和一个数d，求无序数对<i,j>的个数，满足|a_i-a_j|<=d。

思路：先将给定的序列排序，然后放入一个队列中，维护与队首距离<=d的数是哪些。当我们要加入一个数的时候，先将当前队列中与新加入的数距离过远的数出队，同时更新答案，然后将新的数加入队尾。因为我们已经将序列排好序了，所以需要出队的数都在队首，直接判断即可。

考虑数据出队时如何更新答案。我们队列里记录的是比队首大的、符合要求的数（一开始从小到大排序的话），因此答案只需要加上当前队列里的元素数量即可（队首要去掉）。那么比队首小的符合要求的数会漏掉吗？其实并不会，因为<i,j>和<j,i>是相同的，所以这部分已经在之前计算过了。

这样做的复杂度为O(nlogn+n)，过此题无压力

最后，别被样例坑了，输入的数据是无序的，要记得排序（我就是这样在一道红题WA了两次的QAQ，真的是天下最弱了）

贴代码

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=100010;
int n,m,a[N],q[N],fp=1,rp;
long long ans;
int main()
{
    scanf("%d%d",&n,&m);ans=0;
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    sort(a+1,a+n+1);//千万别忘了排序！！！ 
    for(int i=1;i<=n;i++)
    {
        while(fp<=rp&&q[fp]+m<a[i])ans=ans+rp-fp,fp++;//将不合要求的队首出队，同时更新答案 
        q[++rp]=a[i];//将当前数入队 
    }
    int t=rp-fp+1;ans=ans+(long long)t*(t-1)/2;//最后队列里会剩下一些数，别忘了处理 
    printf("%lld\n",ans);return 0;
}