题意

对于两个长度为\(n\)的数组\(a[]\)和\(b[]\)，找到有多少对\(i\)和\(j\)\((ib_i+b_j\)

分析

首先发现如果\(i\)和\(j\)互换不影响不等式，因此对于\(i<j\)这个条件，仅仅是满足二元组\((i,j)\)和\((j,i)\)只算一次

所以将数组打乱顺序后也只需找到所有的二元组\((i,j)\)即可

将不等式移项得到$$a_j-b_j>b_i-a_i$$对于第\(i\)项来说，我们要找到所有的\(j\)满足上述条件

因此选择将\(a_j-b_j\)排序

定义数组\(c[]\)，有\(c[i]=a[i]-b[i]\)

方法一：

对于第\(i\)项，通过二分在\([i+1,n]\)找到最小的\(j\)，满足该不等式，使用\(upper\_bound\)函数即可

则对于第\(i\)项，\(j\)~\(n\)都是满足的，将答案加上\(n-j+1\)，如果没找到，则\(j=n+1\)（\(upper\_bound\)已经满足）

#pragma GCC optimize(3, "Ofast", "inline")

#include <bits/stdc++.h>

#define start ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define ll long long
#define int ll
#define ls st<<1
#define rs st<<1|1
#define pii pair<int,int>
using namespace std;
const int maxn = (ll) 3e5 + 5;
const int mod = 1000000007;
const int inf = 0x3f3f3f3f;

struct node {
    int a, b;
} a[maxn];

int c[maxn];

signed main() {
    start;
    int n;
    cin >> n;
    for (int i = 1; i <= n; ++i)
        cin >> a[i].a;
    for (int i = 1; i <= n; ++i)
        cin >> a[i].b, c[i] = a[i].a - a[i].b;
    sort(c + 1, c + n + 1);
    int ans = 0;
    for (int i = 1; i <= n; ++i) {
        int t = upper_bound(c + i + 1, c + n + 1, -c[i]) - c;
        ans += n - t + 1;
    }
    cout << ans;
    return 0;
}

方法二：

注意到排序后，随\(i\)递增，\(b_i-a_i\)递减，可以发现满足条件的\(j\)递减，因此可采取滑动区间的方式

将\(now\)设置为\(n+1\)

每次循环若\(now>i\&\&c[now - 1] > -c[i]\)，则\(now-1\)也满足不等式，将\(now\)减一

• \(now>i\)，同方法一，\(ans+=n-now+1\)

• \(now=i\)，即\([i+1,n]\)都满足条件，又由于\(j\)是递减的，所以对于后面的\(i\)，\(now<i\)，所以\([i+1,n]\)也满足条件，采取数列求和直接统计答案即可

  #pragma GCC optimize(3, "Ofast", "inline")

  #include

  #define start ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
  #define ll long long
  #define int ll
  #define ls st<<1 #define rs st<<1|1 #define pii pair
  using namespace std;
  const int maxn = (ll) 3e5 + 5;
  const int mod = 1000000007;
  const int inf = 0x3f3f3f3f;

  struct node {
  int a, b;
  } a[maxn];

  int c[maxn];

  signed main() {
  start;
  int n;
  cin >> n;
  for (int i = 1; i <= n; ++i) cin >> a[i].a;
  for (int i = 1; i <= n; ++i) cin >> a[i].b, c[i] = a[i].a - a[i].b;
  sort(c + 1, c + n + 1);
  int ans = 0;
  int now = n + 1;
  for (int i = 1; i <= n; ++i) { while (now > i && c[now - 1] > -c[i])
  --now;
  if (now == i) {
  ans += (n - i + 1) * (n - i) / 2;
  break;
  }
  ans += n - now + 1;
  }
  cout << ans;
  return 0;
  }