奶牛棒球

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

它们正在练习投掷棒球。

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

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

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

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

输入格式

第一行包含整数 $N$4。

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

输出格式

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

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

数据范围

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

输入样例：

1
2
3
4
5
6
5
3
1
10
7
4

输出样例：

1
4

样例解释

四个可能的奶牛三元组为：$1−3−7,1−4−7,4−7−10,1−4−101−3−7,1−4−7,4−7−10,1−4−10$。

分析

此题 $n$ 的范围很小，先按序拍好，直接暴力枚举牵两头牛的位置，然后再找到第三头牛的位置。第三头牛的位置从 $Y$ 到 $Z$ 的距离在 $[XY,2XY]$ 之间，即$[Y + Y - X, Y + 2 \times (Y - X) ] = [2 \times Y - X, 3 \times Y - 2 \times X]$

二分求出左右端点 $[l, r)$ ，$r - l$ 即最后满足要求三元组的数量

利用 STL 二分函数 upper_bound() 与 lower_bound() 直接可以查找

  • lower_bound(x) 返回大于等于x的最小的数的迭代器
  • upper_bound(x) 返回大于x的最小的数的迭代器

复杂度为 $O(n2logn)$，大概是 $1e7$ 的数量级。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main() {
    int n, res = 0;
    cin >> n;
    
    vector<int> a(n);
    for (int& x : a) {
        cin >> x;
    }
    
    sort(a.begin(), a.end());
    
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            res += upper_bound(a.begin(), a.end(), 3 * a[j] - 2 * a[i]) - lower_bound(a.begin(), a.end(), 2 * a[j] - a[i]);
        }
    }
    
    cout << res << endl;
    
    return 0;
}