【数学】Pair of Topics—CF1324D

Pair of Topics—CF1324D

思路

很明显，需要对 $a_i+a_j>b_i+b_j$ 化简：
$a_i-b_i>b_j-a_j$
$a_i-b_i>-(a_j-b_j)$
令 $c_i=a_i-b_i$，则：
$c_i>-c_j$
$c_i+c_j>0$
所求变成：
满足 $i<j$ 且 $c_i+c_j>0$ 的数量。

可以看出，如果没有 $i<j$ 这个要求，那么我们可以对 $c$ 排序，遍历 $i$，对于每一个 $c_i$ 用二分求出满足 $c_i+c_j>0$ 的数量，再求和即可。

其实我们恰恰可以上边的方法求出答案 $res$，然后再执行 $res/=2$ 就是在约束条件 $i<j$ 下的答案。
因为我们用这个方法遍历每一个 $c_i$ 的时候，都多计算了其中 $i^{\prime }>j^{\prime }$ 且 $c_i^{\prime }+c_j^{\prime }>0$ 的数量，而这样的一对 $c_i^{\prime },c_j^{\prime }$ 在 $i(遍历过程中的i)=j^{\prime }(当前的j^{\prime })$ 时都是同时满足两个条件的。所以我们多计算的数量等于应该计算的数量，最终 $res$ 除以 $2$ 就是本题正确的答案。

例如，$i=3,j=2,c_i=666,c_j=-666$，我们在用上百年那个方法的时候会将这种情况也计算在内。但如果将 $i,j$ 对调，我们发现 $i=2,j=3,c_i=-666,c_j=666$ 是同时满足两个条件的。同理，每一个满足两个条件的 $i,j$ 都会其将 $i,j$ 对调后的 $i,j$ 都会错误地被当做正确情况计算在内。

$Code$

#include 
#define int long long
#define sz(a) ((int)a.size())
#define all(a) a.begin(), a.end()
using namespace std;
using PII = pair<int, int>;
using i128 = __int128;
const int N = 2e5 + 10;

int n;
int c[N];

void solve(int Case) {
	cin >> n;
	for (int i = 1; i <= n; i ++) cin >> c[i];
	for (int i = 1; i <= n; i ++) {
		int b; cin >> b;
		c[i] -= b;
	}
	sort(c + 1, c + n + 1);
	
	int res = 0;
	for (int i = 1; i <= n; i ++) {
		int l = 1, r = n;
		while (l < r) {
			int mid = (l + r) / 2;
			if (c[i] + c[mid] > 0) {
				r = mid;
			} else {
				l = mid + 1;
			}
		}
		if (c[i] + c[l] > 0) {
			res += (n - l + 1) - (l <= i);
		}
	}
	cout << "       ";
	cout << res / 2 << "\n";
}

signed main() {
	cin.tie(0)->ios::sync_with_stdio(false);
	int T = 1;
//	cin >> T; cin.get();
	int Case = 0;
	while (++ Case <= T) solve(Case);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48