题意:
给出两组长度为 n n n 的数组 a i , b i a_i,b_i ai,bi,问满足 ( i < j ) a i + a j > b i + b j (i < j) a_i + a_j > b_i + b_j (i<j)ai+aj>bi+bj 有多少对。
移项可得 a i − b i > b j − a j a_i-b_i>b_j-a_j ai−bi>bj−aj ,所以我们只需要求出来每个相对位置的差值,然后差值从小到大排序,只需要找到每个差值后面的比他相反数大的有几个累加即可,这一步我们可以使用二分查找。
AC代码:
const int N = 2e5 + 10;int n, m;int res, cnt, pos;int a[N], b[N], c[N];int main(){sd(n);rep(i, 1, n)sd(a[i]);rep(i, 1, n)sd(b[i]);rep(i, 1, n)c[i] = a[i] - b[i];sort(c + 1, c + n + 1);ll ans = 0;rep(i, 1, n){int pos = upper_bound(c +i+ 1, c + n + 1, -c[i]) - c;ans += (n - pos + 1);}pld(ans);return 0;}