刚开始想到了用map做,O(n)的复杂度AC了,但是我想试下二分,全部WA
#include<iostream>
#include<algorithm>
using namespace std;
const int N=2e6+10;
typedef long long ll;
ll a[N],b[N],n,m,ans,mid,j;
void check(int res,int l,int r){
while(l<=r){
mid=l+r>>1;
if(res+m>a[mid]) l=mid+1;
else r=mid-1;
}
while(res+m==a[l++]) ans++;
}
int main(){
scanf("%lld%lld",&n,&m);
for(int i=0;i<n;i++) scanf("%lld",&a[i]);
sort(a,a+n);
for(int i=0;i<n-1;i++) check(a[i],i+1,n-1);
printf("%lld",ans);
return 0;
}
思路:排序完成后,我们找到它右边第一个符合要求的数字,然后看看这个满足要求的数字有没有和它相等的数字,若有,也能凑一对
结果:WA了,虽然数据可能超了,但是也不可能一组数据都AC不了啊,求大佬指点