啊这样能有76分?$2 \times 10^{5}$ 的数据这么水吗。
你的代码的复杂度是 $O(n^2)$,这是不够优的。需要正解请移步题解。
by cj180202 @ 2023-12-02 20:24:07
可以用二分或map来做。
by cj180202 @ 2023-12-02 20:24:57
@[cj180202](/user/709361) 谢谢大佬!
by ZZYX_18670145320 @ 2023-12-02 20:25:50
@[ZZYX_18670145320](/user/1192648)
手写二分:
```cpp
#include <bits/stdc++.h>
using namespace std;
long long n,C,l,r,mid,baol,baor,ans,tofind,a[200005];//不开longlong见祖宗
int main(){
ios::sync_with_stdio(false);
cin.tie(NULL);cout.tie(NULL);
cin>>n>>C;
for(int i=1;i<=n;i++) cin>>a[i];
sort(a+1,a+n+1);
for(int i=1;i<=n;i++){
tofind=a[i]-C;
l=1;r=i-1;baol=-1;
while(l<=r){
mid=(l+r)>>1;
if(a[mid]>=tofind) baol=mid,r=mid-1;
else l=mid+1;
}
l=1;r=i-1;baor=-1;
while(l<=r){
mid=(l+r)>>1;
if(a[mid]<=tofind) baor=mid,l=mid+1;
else r=mid-1;
}
if(baol!=-1&&baor!=-1) ans+=(baor-baol+1);
}
cout<<ans;
return 0;
}
```
by cj180202 @ 2023-12-02 20:33:06
@[ZZYX_18670145320](/user/1192648)
二分懒人版:
```cpp
#include <bits/stdc++.h>
using namespace std;
long long n,C,tofind,baol,baor,ans,a[200005];
int main(){
ios::sync_with_stdio(false);
cin.tie(NULL);cout.tie(NULL);
cin>>n>>C;
for(int i=1;i<=n;i++) cin>>a[i];
sort(a+1,a+n+1);
for(int i=1;i<=n;i++){
tofind=a[i]-C;
baol=lower_bound(a+1,a+n+1,tofind)-a;
baor=upper_bound(a+1,a+n+1,tofind)-a-1;
if(baol!=n+1&&baor!=n+1) ans+=(baor-baol+1);//这样判断是因为两个函数如果找不到数字,默认返回 n+1
}
cout<<ans;
return 0;
}
```
by cj180202 @ 2023-12-02 20:37:21
@[cj180202](/user/709361) 谢谢大佬,已过
by ZZYX_18670145320 @ 2023-12-03 19:50:36
![](https://fecdn.luogu.com.cn/luogu/logo-single.png?0a231b572e3eb12887faedad7d00e829)
by yjz468 @ 2023-12-09 08:49:30
![](blob:https://toolwa.com/14765c57-7b20-4a0a-8813-b1d48026135c)
by yjz468 @ 2023-12-09 09:03:14
@[ZZYX_18670145320](/user/1192648) 数据太水才让你得了76分,2*10^5这你可以过???要么用二分,要么用双指针
by chenhaoyu_ACAC @ 2023-12-09 12:40:01