在一条坐标轴上，有n头奶牛，第i头奶牛的位置是Xi。FJ现在要选出三头奶牛去比赛，不妨假设选择了奶牛a，b，c。那么必须要满足：
1：Xa＜Xb＜Xc。
2：Xb-Xa≤Xc - Xb≤2×（Xb-Xa）。
你的任务是计算，FJ总共有多少种不同的选择？
第一行，一个整数N。（3≤N≤1000）。
接下来有N行，第i行是整数Xi。
一行，一个整数。
输入样例： 输出样例：
5 4 3 1 10 7 4
其实这道题还算挺简单的。
因为数据范围较大，不能用枚举解决，所以我们可以使用二分查找，枚举两头牛，二分查找一头牛。
二分查找时，我们可以把第二个条件拆分为两个小条件，把“Xb-Xa≤Xc - Xb≤2×（Xb-Xa）”拆分为“Xb-Xa≤Xc-Xb”和“Xc-Xb≤2×(Xb-Xa)”
这样我们用两个二分查找，先找满足“Xb-Xa≤Xc-Xb”的Xc有多少，再找满足“Xc-Xb≤2×(Xb-Xa)”的Xc有多少，把两个结果相减，就能得到同时满足两个条件的Xc的数量了
具体程序如下：
#include<iostream> #include<cstdio> #include<algorithm> using namespace std; int n,s,q[10000000],t,ans,m,temp,ans1,ans2,l,r; int main() { scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%d",&q[i]); } sort(q+1,q+1+n); for(int i=1;i<=n;i++) { for(int j=i+1;j<=n;j++) { int left=0,right=n+1,mid; while(left+1<right) { mid=(left+right)/2; if(q[j]-q[i]>q[mid]-q[j]) left=mid; else right=mid; } ans1=left; left=0,right=n+1; while(left+1<right) { mid=(left+right)/2; if(q[mid]-q[j]>2*(q[j]-q[i])) right=mid; else left=mid; } ans2=left; t+=ans2-ans1; } } cout<<t; }
原文：https://www.cnblogs.com/2021-yanghaoran/p/10421982.html