Codeforces1324D Pair of Topics (思维 + 二分)

题目链接: Pair of Topics

大致题意

给定两个数组a和b, 要求找出所有满足i < j 并且 ai + aj > bi + bj 的所有数对.

解题思路

我们不难想到先对等式变形, 不妨设ci = ai - bi, 则原式变为ci > -cj <==> ci + cj > 0.

这是什么? 权值线段树!!!. 好吧, 我又来了个1A权值线段树. 竟和 1538C 如此的相似.

我们发现, 我们可以去枚举每一个ci, 通过二分的方式找到符合的cj数量.

为了避免重复计算答案, 我们不妨假设ci > cj. 这样假设每次从index位置起, j ∈ [index, n] 均成立, 我们累加结果[i, index) 即可.

AC代码

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 1; i <= (n); ++i)
using namespace std;
typedef long long ll;
const int N = 2E5 + 10;
int a[N];
int main()
{
int n; cin >> n;
rep(i, n) scanf("%d", &a[i]);
rep(i, n) {
int x; scanf("%d", &x);
a[i] -= x;
}
sort(a + 1, a + 1 + n);
ll res = 0;
rep(i, n) {
int index = upper_bound(a + 1, a + 1 + n, -a[i]) - a;
res += max(i - index, 0);
}
cout << res << endl;
return 0;
}

END

最后

以上就是鳗鱼钢笔为你收集整理的Codeforces1324D Pair of Topics (思维 + 二分)的全部内容，希望文章能够帮你解决Codeforces1324D Pair of Topics (思维 + 二分)所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。