AcWing 1945. 奶牛棒球
原题链接
简单
作者:
背书包的小新
,
2022-01-15 16:32:59
,
所有人可见
,
阅读 179
二分
#include <bits/stdc++.h>
using namespace std;
int n;
int a[1005];
int ans = 0;
int main()
{
freopen("in.in", "r", stdin);
cin >> n;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
}
sort(a + 1, a + n + 1);
for (int i = 1; i <= n - 2; i++)
{
for (int j = i + 1; j <= n - 1; j++)
{
int k = a[j] - a[i];
int l = j + 1, r = n;
while (l < r)
{
int mid = (l + r) >> 1;
if (a[mid] - a[j] >= k)
r = mid;
else
l = mid + 1;
}
if (a[r] - a[j] < k)
continue;
int k1 = r;
l = k1, r = n;
while (l < r)
{
int mid = (l + r + 1) >> 1;
if (a[mid] - a[j] <= 2 * k)
l = mid;
else
r = mid - 1;
}
if (a[r] - a[j] > 2 * k)
continue;
int k2 = r;
// cout << a[i] << " " << a[j] << " " << k << " " << k1 << " " << k2 << endl;
ans += k2 - k1 + 1;
}
}
cout << ans;
return 0;
}
给个关注呗,本人无条件互粉