CodeForces 1324D Pair of Topics

题意

对于两个长度为$n$的数组$a[]$和$b[]$，找到有多少对$i$和$j(i<j)$，满足$a_i+a_j>b_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 <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;
    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;
}