算法1
(暴力枚举+二分查找)
先暴力枚举X和Y 然后通过条件确定中间的范围 然后找几头奶牛的位置在这个范围中间
时间复杂度
O(n^2*logn)
C++ 代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e3+5;
int a[N];
int main()
{
int n;
cin>>n;
int ans=0;
for (int i = 0; i < n; i ++ ) cin>>a[i];
sort(a,a+n);
int l,r; //l=左边界 r=右边界
for (int i = 0; i < n-2; i ++ ){
for (int j = i+1; j < n-1; j ++ ){
l=lower_bound(a,a+n,a[j]+a[j]-a[i])-a; //lower 找大于等于该数 输出地址 所以-a 就输出下标
r=upper_bound(a,a+n,a[j]+2*(a[j]-a[i]))-a; //upper 找大于该数 输出地址 如果用lower找那还要判断这个点是不是在右边界
ans+=r-l; //简化前:r-1 此时才是我们需要的下标 r-1-l+1 加上减去l 此时多减了一个l点 所以是r-l
}
}
cout<<ans<<endl;
}