农夫约翰的 $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 表示从 $X$ 到 $Y$ 的距离。

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

输入样例：

5
3
1
10
7
4

输出样例：

4

样例解释
四个可能的奶牛三元组为： $1-3-7,1-4-7,4-7-10,1-4-10$ 。

解题思路

1. 排序（升序排列）
2. 枚举 $x,y$
3. 然后根据双指针特性（单调性）$or$ 二分 找 $z$ 的范围
4. 找第一个满足 $z-y>=y-z$ 的数，找第一个满足 $z-y>2\ast (y-z)$ 的数 $[l,r]$
5. $z$ 的取值就是 $[l,r-1]$

双指针 49ms

#include<iostream>
#include<algorithm>

using namespace std;

const int N = 1010;

int p[N];

int main(){
    
    int n, res = 0;
    
    cin >> n;
    
    for(int i = 0; i < n; i++) cin >> p[i];
    
    sort(p, p + n);
    
    for(int i = 0; i + 2 < n; i++){
        for(int j = i + 1, l = j + 1, r = j + 1; j + 1 < n; j++){
            
            while(l < n && p[l] - p[j] < p[j] - p[i]) l++;
            while(r < n && p[r] - p[j] <= 2 * (p[j] - p[i])) r++;
            res += (r - l);
        }
    }
    
    cout << res << endl;
    return 0;
}

二分 742ms

#include<iostream>
#include<algorithm>

using namespace std;

const int N = 1010;

int p[N];

int main(){
    
    int n, res = 0;
    
    cin >> n;
    
    for(int i = 0; i < n; i++) cin >> p[i];
    
    sort(p, p + n);
    
    for(int i = 0; i + 2 < n; i++){
        for(int j = i + 1; j + 1 < n; j++){
            
            int l = lower_bound(p, p + n, 2 * p[j] - p[i]) - p;
            int r = upper_bound(p, p + n, 3 * p[j] - 2 * p[i]) - p;
            
            res += (r - l);
        }
    }
    
    cout << res << endl;
    return 0;
}

最后

以上就是动人小松鼠为你收集整理的奶牛棒球（寒假每日一题 13）解题思路的全部内容，希望文章能够帮你解决奶牛棒球（寒假每日一题 13）解题思路所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。