1945.奶牛棒球

1945. 奶牛棒球

题目描述：

农夫约翰的 $N$ 头奶牛排成一排，每头奶牛都位于数轴中的不同位置上。

它们正在练习投掷棒球。

农夫约翰观看时，观察到一组三头牛 $(X,Y,Z)$ 完成了两次成功的投掷。

牛 $X$ 把球扔给她右边的牛 $Y$ ，然后牛 $Y$ 把球扔给她右边的牛 $Z$ 。

约翰指出，第二次投掷的距离不少于第一次投掷的距离，也不超过第一次投掷的距离的两倍。

请计算共有多少组牛 $(X,Y,Z)$ 可能是约翰所看到的。

输入格式

第一行包含整数 $N$ 。

接下来 $N$ 行，每行描述一头牛的位置。

输出格式

输出奶牛三元组 $(X,Y,Z)$ 的数量。

$(X,Y,Z)$ 需满足， $Y$ 在 $X$ 的右边， $Z$ 在 $Y$ 的右边，并且从 $Y$ 到 $Z$ 的距离在 $[XY,2XY]$ 之间，其中 $XY$ 表示从 $XX$ 到 $YY$ 的距离。

数据范围

$3≤N≤1000$
奶牛所在的位置坐标范围 $[0,108]$ 。

输入样例：

5
3
1
10
7
4

输出样例：

4

题解：

很简单，排序，枚举前两个，然后二分找最后一个，注意二分的时候，要把距离转化为坐标。

查找大于等于：lower_bound()

查找小于等于：upper_bound() - 1

查找大于：upper_bound()

查找小于：lower_bound() - 1

使用 lower_bound() 和 upper_bound() 可以查找出所有的情况。

代码：

using namespace std;
using namespace FAST_IO;
const ll mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const ll INF_LL = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-5;
const int maxn = 1e3 + 10;
const int maxm = 1e5 + 10;
int t, n, m, k;
int a[maxn];
int main()
{
// #define COMP_DATA
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
#endif
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }
    sort(a + 1, a + 1 + n);
    int ans = 0;
    for (int i = 1; i <= n; i++)
    {
        for (int j = i + 1; j <= n; j++)
        {
            int keyl = 2 * a[j] - a[i];
            int keyr = 3 * a[j] - 2 * a[i];
            int l = lower_bound(a + j + 1, a + 1 + n, keyl) - a;
            int r = upper_bound(a + j + 1, a + 1 + n, keyr) - a;
            // [l, r - 1]
            // ans += r - 1 - l + 1;
            ans += r - l;
        }
    }
    cout << ans << endl;
    return 0;
}