AcWing 1945. 奶牛棒球 java (枚举+双指针+二分)
原题链接
简单
作者:
yoiy-sk
,
2022-01-15 18:16:40
,
所有人可见
,
阅读 305
java - 枚举+双指针+二分
import java.util.*;
public class Main{
static int N = 10000010;
static int[] q = new int[N];
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
for (int i = 0; i < n; i++) {
q[i] = sc.nextInt();
}
Arrays.sort(q);
int sum = 0;
for(int i = 1 ; i < q.length -1; i++){
int l = i - 1;
while (q[l] !=0 && l >= 0 ){
int xy = q[i] - q[l];
int L = findL(q[i] + xy);
int R = findR(q[i] + 2*xy);
if( L < R) {
sum += R-L+1;
l--;
}else if(L == R){
if( q[R] - q[i] >= xy && q[R] -q[i] <= 2*xy){
sum += R-L+1;
}
l--;
}else{
l--;
}
}
}
System.out.println(sum);
}
//二分找边界,即每当固定x 和y 时,找出对满足条件z的边界
//找出左区间边界 即 xy < u
static int findL(int u){
int l = 0 ,r = q.length-1;
while (l < r){
int mid = l + r >> 1;
if(q[mid] >= u){
r = mid;
}else{
l = mid + 1;
}
}
return r;
}
//找出右区间边界 即 u<2xy
static int findR(int u){
int l = 0 ,r = q.length-1;
while (l < r){
int mid = l + r +1 >> 1;
if(q[mid] <= u){
l = mid;
}else{
r = mid - 1;
}
}
return r;
}
}