B - Binary Search Aizu - ALDS1_4_B
2-Day2-B
Search II
You are given a sequence of n integers S and a sequence of different q integers T. Write a program which outputs C, the number of integers in T which are also in the set S.
Input
In the first line n is given. In the second line, n integers are given. In the third line q is given. Then, in the fourth line, q integers are given.
Output
Print C in a line.
Constraints
Elements in S is sorted in ascending order
n ≤ 100000
q ≤ 50000
0 ≤ an element in S ≤ 109
0 ≤ an element in T ≤ 109
Sample Input 1
5
1 2 3 4 5
3
3 4 1
Sample Output 1
3
Sample Input 2
3
1 2 3
1
5
Sample Output 2
0
Sample Input 3
5
1 1 2 2 3
2
1 2
Sample Output 3
2
Notes
题意:
给定一个n个整数的序列S和一个不同q个整数的序列T。写一个程序,输出C,T中的整数数,也在集合S中。
思路:看见他的题目名没。二分查找binary_search()就完了。
代码如下:
#include<cstdio> #include<queue> #include<cmath> #include<cstring> #include<iostream> #include<algorithm> using namespace std; int main(void) { int ss[100001],qs,sum=0; int s; cin>>s; for(int i=0;i<s;i++) cin>>ss[i]; int q; cin>>q; for(int i=0;i<q;i++) { cin>>qs; if(binary_search(ss,ss+s,qs)) sum++; } cout<<sum<<endl; }