原题链接:传送门
题意:数组a和b中,有几个ai+aj>bi+bj
思路:我们对这个式子整理0>(bi-ai)+(bj-aj),所以我们可以选择双指针或二分去搜答案,那么这里我们可以思考一下,怎么去二分得到答案呢?很显然,我们二分选择搜bi-ai,那么最大的bj-ai=-(bi-ai),lower_bound去搜索即可。
#include <bits/stdc++.h>#define int long longtypedef long long LL;signed main(){std::ios::sync_with_stdio(false);std::cin.tie(nullptr);int n;std::cin >> n;std::vector<int> a(n), b(n);for (int &ai : a) std::cin >> ai;for (int i = 0; i < n; i++){int x;std::cin >> x;b[i] = x - a[i];}std::sort(b.begin(), b.end());int ans = 0;for (int i = 0; i < n; i++){int j = std::lower_bound(b.begin() + i + 1, b.end(), -b[i]) - b.begin() - 1;ans += j - i;}std::cout << ans << "\n";return 0;}