The next lecture in a high school requires two topics to be discussed. The i-th topic is interesting by ai units for the teacher and by bi units for the students.
The pair of topics i and j (i<j) is called good if ai+aj>bi+bj (i.e. it is more interesting for the teacher).
Your task is to find the number of good pairs of topics.
Input
The first line of the input contains one integer n (2≤n≤2⋅105) — the number of topics.
The second line of the input contains n integers a1,a2,…,an (1≤ai≤109), where ai is the interestingness of the i-th topic for the teacher.
The third line of the input contains n integers b1,b2,…,bn (1≤bi≤109), where bi is the interestingness of the i-th topic for the students.
Output
Print one integer — the number of good pairs of topic.
Examples Input
5
4 8 2 6 2
4 5 4 1 3
Output
7
Input
4
1 3 2 4
1 3 2 4
Output
0
题目大意:给出两个数组,求ai+aj>bi+bj的种数。
解题思路:ai+aj>bi+bj可以转化为ai-bi+aj-bj>0的种数。我们开三个数组,一个用于存放a,一个用于存放b,最后一个数组c用来存放ai-bi的值。我们给c数组从小到大排个序,每次查找比 -ci 大的值,这样ci+cj一定大于0。
PS:其实不用考虑 i<j 因为 i != j 所以随便找出两个数,他们的编号必须是一个大一个小。AC代码:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33#include <cstdio> #include <iostream> #include <algorithm> using namespace std; const int _max=2e5+50; using LL = long long; LL a[_max],b[_max],c[_max]; int main() { int n; cin>>n; for(int i=0;i<n;i++) cin>>a[i]; for(int i=0;i<n;i++) { cin>>b[i]; c[i]=a[i]-b[i]; } sort(c,c+n); LL ans=0; for(int i=0;i<n;i++) { int x=upper_bound(c+i+1,c+n,-c[i])-c; if(x>=n)//如果找不到返回最后一个地址+1 continue; else ans+=n-x;//因为一共n个数,所以用n-x就得到数量了 } cout<<ans<<endl; //system("pause"); return 0; }
最后
以上就是精明季节最近收集整理的关于CodeForces 1324D - Pair of Topics(二分查找)的全部内容,更多相关CodeForces内容请搜索靠谱客的其他文章。
发表评论 取消回复