Luobuyu's Blog

0%

1945.奶牛棒球

发表于 分类于 ， 热度： ℃ 评论：
本文字数： 1.3k 阅读时长 ≈ 1 分钟
很简单的一道题。

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] $ 。

输入样例：

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

输出样例：

1
4

题解：

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

查找大于等于：lower_bound()

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

查找大于：upper_bound()

查找小于：lower_bound() - 1

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

代码：

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
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;
}