emmm代码找不到了,谁能发个正解
by Z_C_M @ 2019-04-11 18:30:47
找到了,贴个我的代码
```c
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;
int main(){
long int m,n=0,r,i=0,j;
cin>>m>>r;
long int s[m];
while(i<m){
cin>>s[i];
i++;
}
i=0;
sort(s,s+m);
while(i<m){
j=i;
while(j<m){
if(s[i]+r==s[j])n++;
j++;
}
i++;
}
cout<<n<<endl;
return 0;
}
```
by Z_C_M @ 2019-04-11 20:16:05
有没有大佬讲一下
by Z_C_M @ 2019-04-11 20:16:19
你的时间复杂度太高了,把每一个跟其他的都匹配一遍的复杂度是O(n^2)。
你可以变一下形,把A-B=C变成B+C=A,用map标记一下每一个数的个数,这样就只要枚举每一个B看看A有几个就行了,复杂度O(n)。
贴个代码(其实还可以用指针优化一下)
```cpp
// luogu-judger-enable-o2
#include<bits/stdc++.h>
using namespace std;
map<int,int>mp;
int a[200005];
int main(){
std::ios::sync_with_stdio(false);//快读
long int n,c,ans=0,i=0;
cin>>n>>c;
while(i<n){i++;cin>>a[i];mp[a[i]]++;}
for(int i=1;i<=n;i++)ans+=mp[a[i]+c];
cout<<ans;
return 0;
}
```
by 天南月 @ 2019-05-04 20:02:20