当前位置：首页 > news >正文

【数学】Pair of Topics—CF1324D

news 来源：原创 2024/5/20 4:12:51

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^{'} > j^{'}$ 且 $c_i' + c_j' > 0$ 的数量，而这样的一对 $c_i', c_j'$ 在 $i (遍历过程中的 i) = j^{'} (当前的 j^{'})$ 时都是同时满足两个条件的。所以我们多计算的数量等于应该计算的数量，最终 $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$ 都会错误地被当做正确情况计算在内。

$C o d e$

#include <bits/stdc++.h>
#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;
}