Information
- ID
- 279
- Time
- 1000ms
- Memory
- 256MiB
- Difficulty
- 7
- Tags
- # Submissions
- 301
- Accepted
- 58
- Uploaded By
方法一
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,c,l,r,ans;
ll a[1000005];//数据有点大
int main()
{
cin>>n>>c;
for(int i=0;i<n;++i)
{
cin>>a[i];
}
sort(a,a+n);
for(int i=0;i<n;++i)
{
l=lower_bound(a,a+n,a[i]+c)-a;//不懂的建议百度
r=upper_bound(a,a+n,a[i]+c)-a;
ans+=r-l;
}
cout<<ans;
return 0;
}
方法二 (和做法一思路一样)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,x,h;
int a[1000000];
int find1(int x)//找小于等于a[i]-C的数的函数
{
int l=0,r=n+1,mid;
while(l+1<r)
{
mid=(l+r)/2;
if(a[mid]<=x)l=mid;
else r=mid;
}
return l;
}
int find2(int x)
{
int l=0,r=n+1,mid;
while(l+1<r)
{
mid=(l+r)/2;
if(a[mid]<x) l=mid;
else r=mid;
}
return l;
}
int main()
{
cin>>n>>x;
for(int i=1; i<=n; i++)
{
cin>>a[i];
}
sort(a+1,a+1+n);
for(int i=1; i<=n; i++)
{
h+=find1(a[i]+x)-find2(a[i]+x);
}
cout<<h;
return 0;
}
By signing up a 追梦算法网 universal account, you can submit code and join discussions in all online judging services provided by us.