左闭右开区间
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1010;
int n;
int a[N];
int checkl(int l, int r, int k, int j)
{
while (l < r)
{
int mid = l + r >> 1;
if (a[mid] - a[j] >= k)
r = mid;
else
l = mid + 1;
}
return l;
}
int checkr(int l, int r, int k, int j)
{
while (l < r)
{
int mid = l + r >> 1;
if (a[mid] - a[j] <= 2 * k)
l = mid + 1;
else
r = mid;
}
return l;
}
int main()
{
cin >> n;
for (int i = 0; i < n; i ++ )
cin >> a[i];
sort(a, a + n);
int res = 0;
for (int i = 0; i < n; i ++ )
{
for (int j = i + 1; j < n; j ++ )
{
int k = a[j] - a[i];
int l = checkl(j, n, k, j);
int r = checkr(j, n, k, j);
if (l < r)
res += r - l;
}
}
cout << res << endl;
return 0;
}
左闭右闭区间
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1010;
int n;
int a[N];
int checkl(int l, int r, int k, int j)
{
while (l < r)
{
int mid = l + r >> 1;
if (a[mid] - a[j] >= k)
r = mid;
else
l = mid + 1;
}
return l;
}
int checkr(int l, int r, int k, int j)
{
while (l < r)
{
int mid = l + r + 1 >> 1;
if (a[mid] - a[j] <= 2 * k)
l = mid;
else
r = mid - 1;
}
return l;
}
int main()
{
cin >> n;
for (int i = 0; i < n; i ++ )
cin >> a[i];
sort(a, a + n);
int res = 0;
for (int i = 0; i < n; i ++ )
{
for (int j = i + 1; j < n; j ++ )
{
int k = a[j] - a[i];
int l = checkl(j + 1, n - 1, k, j);
int r = checkr(j + 1, n - 1, k, j);
if (a[l] - a[j] < k || a[r] - a[j] > 2 * k)
continue;
if (l <= r)
res += r - l + 1;
}
}
cout << res << endl;
return 0;
}