Pair of Topics

链接

题目链接

题意

老师：数组 a

学生：数组 b

如果 ai + aj > bi + bj，则 i 和 j 主题是好的主题对，求好的主题对的数量

思路

将 a、b 数组相减，结果保留在 a 数组中，选取 2 个下标，这 2 个位置和大于 0 便是好的主题对，因此对 a 数组升序之后，枚举第一个主题，再二分答案即可（假如下标 1 和 k 对应的主题是好的主题对，则 1 和 [2, k] 对应的主题全是好的主题对）

代码

#include <bits/stdc++.h>
#define pii pair<int, int>
typedef long long ll;
using namespace std;
#define ioClose() ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define endl '\n'const int maxn = 2e5 + 5;
const int mod = 998244353;
int a[maxn];
bool cmp(int a, int b) {
    return a > b;
}
bool check(int m, int start) {
    return a[m] + a[start] > 0;
}
int main() {
    int T = 1;// cin >> T;while (T--) {
    int n;cin >> n;for (int i = 1; i <= 2 * n; i++) {
    if (i <= n) {
    cin >> a[i];} else {
    int temp;cin >> temp;a[i - n] -= temp;}}sort(a + 1, a + 1 + n, cmp);ll sum = 0;for (int start = 1; start <= n - 1; start++) {
    int l = start, r = n;while (l < r) {
    int m = l + r + 1 >> 1;if (check(m, start)) l = m;else r = m - 1;}// cout << "start == " << start << "\tl == " << l << endl;// l - start 主题对的数量sum += (l - start);}cout << sum << endl;}return 0;
}