AcWing 1945. 奶牛棒球 CPP 排序+双指针+二分 n2logn
原题链接
简单
作者:
第一万零一次AC
,
2022-01-15 17:07:15
,
所有人可见
,
阅读 203
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 1005;
int a[N],n,ans;
int main()
{
cin>>n;
for(int i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
sort(a,a+n);//首先升序对所有牛的位置进行排序
for(int i=0;i<n;i++)
{
for(int j=i+1;j<n;j++)//枚举x和y,从y+1开始二分查找距离在[xy,2xy]的位置
{
//首先在左边二分找出大于等于xy的第一个点
int l = j,r = n-1;
int dis = a[j] - a[i];
while(l<r)
{
int mid = l+r>>1;
if(a[mid] - a[j] >= dis) r = mid;
else l = mid + 1;
}
int L = l;
if(a[L] - a[j] < dis || a[L] - a[j] > 2*dis) continue;
//接着在右边二分查找出小于等于2xy的第一个点
l = j,r = n-1;
while(l<r)
{
int mid = l+r+1>>1;
if(a[mid] - a[j] <= 2*dis) l = mid;
else r = mid - 1;
}
int R = l;
if(a[R] - a[j] > 2*dis || a[R] - a[j] < dis) continue;
//cout<<a[i]<<" "<<a[j]<<":";
//for(int k = L;k<=R;k++) cout<<a[k]<<" ";
//puts("");
ans += R - L + 1;//[L,R]之间所有的点一定满足条件
}
}
cout<<ans<<endl;
}