题目描述
双指针算法,先把数组排序。
从小到大枚举i,确定i之后向后移动k,直到临界情况并记录结果到ans。
然后,保持k不动,i向后移动一格,可以保证i到k的几个都是可以到达的,则之间可以形成 新的 k-i-1 个pair。
可以把O(n^2)的复杂度降到O(n)左右。
C++ 代码
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<cmath>
using namespace std;
typedef long long LL;
const int N=1e5+10;
int a[N];
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
int n,k;
scanf("%d %d",&n,&k);
for(int i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
sort(a,a+n);
LL ans=0;
int cnt=0;
for(int i=0;i<n;i++)
{
while(abs(a[i]-a[cnt])<=k && cnt<n) cnt++;
ans=ans+cnt-i-1;
}
cout<<ans<<endl;
/*
int site1=0,site2=0;
for(int i=0;i<n;i++)
{
int l=0,r=n-1;
while(l<r)
{
int mid=(l+r+1)>>1;
if(abs(a[mid]-a[i])<=k) l=mid;
else r=mid-1;
}
site1=l;
l=0,r=n-1;
while(l<r)
{
int mid=(l+r)>>1;
if(abs(a[mid]-a[i])>=k) r=mid;
else l=mid+1;
}
site2=l;
}
cout<<site1-site2<<endl;
*/
}
return 0;
}