Cu Ball
TLE on #2 #3
```cpp
#include<cstdio>
#include<algorithm>
using namespace std;
int bs(int a[],int n,int x){
int low=1,high=n,mid;
while(low<=high){
mid=(low+high)/2;
if(x==a[mid]) return mid;
else if(x<a[mid]) high=mid-1;
else low=mid+1;
}
return -1;
}
int cnt(int a[],int n,int x){
int ans=0;
for(int i=1;i<=n;i++){
if(a[i]==x) ans++;
}
return ans;
}
int main(){
int ans=0,n,c,s[200001];
scanf("%d%d",&n,&c);
for(int i=1;i<=n;i++){
scanf("%d",&s[i]);
}
sort(s+1,s+n+1);
for(int i=1;i<=n;i++){
if(bs(s,n,s[i]-c)!=-1) ans+=cnt(s,n,s[i]-c);
}
printf("%d",ans);
return 0;
}
```
by _TCR_ @ 2024-03-25 18:21:56
@[bu_chi_suan](/user/1314163) `//对得到的数组从小到大排序 `
$\Theta(n^2)$
by XuYueming @ 2024-03-25 18:23:01
@[_TCR_](/user/483466) @[bu_chi_suan](/user/1314163) 二分的统计是 $\Theta(n)$ 的，为何每次都要扫一遍统计次数？
by XuYueming @ 2024-03-25 18:24:33
@[XuYueming](/user/728079) 大佬，cnt放在在那个二分函数中和放到函数外，花费的时间不一样吗？我想的就是每次调用二分函数找到后就进行一次统计
by bu_chi_suan @ 2024-03-25 18:31:19
@[_TCR_](/user/483466) 感谢你的代码，我把冒泡排序改成sort后2，3不会超时了，但4依然超时
by bu_chi_suan @ 2024-03-25 18:40:56
~~这道题有那么难吗？？？~~
**勿抄**
```
#include <bits/stdc++.h>
int a[200010], n, c;
long long ans = 0;
using namespace std;
int findx(int k) { // 找到第一次出现的位置
int l = 1, r = n, ans = -1;
while (l <= r) {
int mid = (r+l)/2;
if (a[mid]==k) { // 如果中间的数字等于要找的
ans=mid; // 记录答案位置
r=mid-1; // 局限在左区间
} else if ( a[mid]>k) // 如果中间数字大于要找的
r=mid-1; // 局限在左区间
else // 如果中间数字小于于要找的
l=mid+1; // 局限在右区间
}
return ans;
}
int findy(int k) { // 找到第一次出现的位置
int l = 1, r = n, ans = -1;
while (l <= r) {
int mid = (r+l)/2;
if (a[mid]==k) { // 如果中间的数字等于要找的
ans=mid; // 记录答案位置
l=mid+1; // 局限在左区间
} else if ( a[mid]>k) // 如果中间数字大于要找的
r=mid-1; // 局限在左区间
else // 如果中间数字小于于要找的
l=mid+1; // 局限在右区间
}
return ans;
}
int main() {
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++) {
int x = findx(a[i] + c);
int y = findy(a[i] + c);
if(x == -1) continue;
ans += y-x+1;
}
cout << ans; // __输出答案
}
```
by HAha201205221633 @ 2024-03-25 18:47:30
@[HAha201205221633](/user/892365) 大佬，谢谢！我没想到可以直接分别找到首个和最后一个，直接就找到首个后遍历找个数了
by bu_chi_suan @ 2024-03-25 19:35:32