1500字范文,内容丰富有趣,写作好帮手!
1500字范文 > Codeforces 1324 D. Pair of Topics(二分)

Codeforces 1324 D. Pair of Topics(二分)

时间:2021-05-05 09:39:38

相关推荐

Codeforces 1324 D. Pair of Topics(二分)

题意:

给出两组长度为 n n n 的数组 a i , b i a_i,b_i ai​,bi​,问满足 ( i < j ) a i + a j > b i + b j (i < j) a_i + a_j > b_i + b_j (i<j)ai​+aj​>bi​+bj​ 有多少对。

移项可得 a i − b i > b j − a j a_i-b_i>b_j-a_j ai​−bi​>bj​−aj​ ,所以我们只需要求出来每个相对位置的差值,然后差值从小到大排序,只需要找到每个差值后面的比他相反数大的有几个累加即可,这一步我们可以使用二分查找。

AC代码:

const int N = 2e5 + 10;int n, m;int res, cnt, pos;int a[N], b[N], c[N];int main(){sd(n);rep(i, 1, n)sd(a[i]);rep(i, 1, n)sd(b[i]);rep(i, 1, n)c[i] = a[i] - b[i];sort(c + 1, c + n + 1);ll ans = 0;rep(i, 1, n){int pos = upper_bound(c +i+ 1, c + n + 1, -c[i]) - c;ans += (n - pos + 1);}pld(ans);return 0;}

本内容不代表本网观点和政治立场,如有侵犯你的权益请联系我们处理。
网友评论
网友评论仅供其表达个人看法,并不表明网站立场。