题目链接

1945. 奶牛棒球 - AcWing题库

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

它们正在练习投掷棒球。

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

牛 XX 把球扔给她右边的牛 YY，然后牛 YY 把球扔给她右边的牛 ZZ。

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

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

输入格式

第一行包含整数 NN。

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

输出格式

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

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

数据范围

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

输入样例：

5
3
1
10
7
4

输出样例：

4

样例解释

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

思路：

        第三头牛满足

------>Y-X<=Z-Y<=2Y-2X

------->Z>=2Y-x,Z<=3Y-2X

枚举第一头牛

枚举第二头牛

那么第三头牛就是符合Z的条件的牛的

二分：

#include
#define int long long
using namespace std;
const int N=1100;
int a[N];
int n;signed main() {cin>>n;for(int i=0; i>a[i];}sort(a,a+n);int ans=0;//记录答案for(int i=0; i=2 * a[j] - a[i]的牛的位置int l=lower_bound(a,a+n,2 * a[j] - a[i])-a;//从数组的begin位置到end-1位置二分查找第一个大于num的数字int r=upper_bound(a, a + n, 3 * a[j] - 2 * a[i]) - a;//那么我们找到这个r，只需要r-1就是距离在<= 3 * a[j] - 2 * a[i]范围内的了ans+=r-l;}}cout<

#include
#define int long long
using namespace std;
const int N=1100;
int a[N];
int n;signed main() {cin>>n;for(int i=0; i>a[i];}sort(a,a+n);int ans=0;//记录答案for(int i=0; i