思路
排序 + 二分/双指针
过程
代码
#include <iostream>
#include <algorithm>
using namespace std;
using LL = long long;
const int N = 2e5 + 10;
int n, l, r, a[N];
int main()
{
cin >> n >> l >> r;
for(int i = 0;i < n;i ++) cin >> a[i];
sort(a, a + n);
LL ans = 0;
for(int i = 0;i < n;i ++)
{
int x = i + 1, y = n - 1;
while(x < y)
{
int mid = (x + y) >> 1;
if(a[mid] >= a[i] + l) y = mid;
else x = mid + 1;
}
int begin = 0;
if(a[x] < a[i] + l) begin = x + 1;
else begin = x;
x = i + 1, y = n - 1;
while(x < y)
{
int mid = (x + y + 1) >> 1;
if(a[mid] > a[i] + r) y = mid - 1;
else x = mid;
}
int end = x;
ans += end - begin + 1;
}
cout << ans << endl;
return 0;
}
#include <iostream>
#include <algorithm>
using namespace std;
using LL = long long;
const int N = 2e5 + 10;
int n, l, r, a[N];
LL find(int x)
{
int i = 0, j = 0;
LL ans = 0;
while(j < n)
{
while(a[j] - a[i] > x) i ++;
ans += j - i;
j ++;
}
return ans;
}
int main()
{
cin >> n >> l >> r;
for(int i = 0;i < n;i ++) cin >> a[i];
sort(a, a + n);
cout << find(r) - find(l - 1) << endl;
return 0;
}