思想
前缀和+双指针,cal()求所有a[i]+a[j]>x的个数。其双指针的部分与ACWing 800 数组元素的目标和很像
代码
import java.io.*;
import java.util.Arrays;
public class Main {
static StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
static PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
static int[] a = new int[100010];
static int n;
public static void main(String[] args)throws IOException{
n = nextInt();
int L = nextInt(), R = nextInt();
for(int i=0; i<n; i++) a[i] = nextInt();
Arrays.sort(a, 0, n);
out.println(cal(R)-cal(L-1));
out.flush();
out.close();
}
//当i<j时,计算有多少对a[i]+a[j]<=x
public static long cal(int x){
long ans = 0;
int l = 0, r=n-1;
while(l<r){
while(l<r && a[l]+a[r]>x) r--;
ans += (long)(r-l);
l++;
}
return ans;
}
public static int nextInt()throws IOException{
in.nextToken();
return (int)in.nval;
}
}