URAL 1196. History Exam (二分)
二分 history URAL
2023-09-11 14:20:43 时间
1196. History Exam
Time limit: 1.5 second
Memory limit: 64 MB
Memory limit: 64 MB
Professor of history decided to simplify the examination process. At the exam, every student should write a list of historic dates she knows (she should write the years only and, of course, must be
able to explain what event took place in this or that year). Professor has a list of dates that students must know. In order to decide upon the student's mark, Professor counts the number of dates in the student's list that are also present in his list. The
student gets her mark according to the number of coincidences.
Your task is to automatize this process. Write a program that would count the number of dates in the student's list that also occur in Professor's list.
Input
The first line contains the number N of dates in Professor's list, 1 ≤ N ≤ 15000. The following Nlines contain this list, one number per line. Each date is a positive integer
not exceeding 109. Professor's list is sorted in non-descending order. The following line contains the number M of dates in the student's list, 1 ≤ M ≤ 106.
Then there is the list itself; it is unsorted. The dates here satisfy the same restriction. Both in Professor's and in the student's lists dates can appear more than once.
Output
Output the number of dates in the student's that are also contained in Professor's list.
Sample
input | output |
---|---|
2 1054 1492 4 1492 65536 1492 100 |
2 |
题意:找出第一和第二个序列中都出现(同意反复累加)过的字符个数。
解析:因为第一个有序的,所以我们遍历第二个序列的同一时候对第一个序列二分搜索答案。
PS:本题有个非常诡异的现象:G++跑了1.5s+。可是VC++居然才跑0.343s。
。。貌似仅仅有VC++才干过。
AC代码:
#include <cstdio> using namespace std; int a[15002]; int main(){ #ifdef sxk freopen("in.txt", "r", stdin); #endif // sxk int n, m, ans, foo; while(scanf("%d", &n)==1){ ans = 0; for(int i=0; i<n; i++) scanf("%d", &a[i]); scanf("%d", &m); for(int i=0; i<m; i++){ scanf("%d", &foo); int l = 0, r = n - 1, m; if(foo < a[0] || foo > a[n-1]) continue; else if(foo == a[0] || foo == a[n-1]){ ans ++; continue; } while(l <= r){ m = (r - l) / 2 + l; if(a[m] == foo){ ans ++; break; } if(a[m] < foo) l = m + 1; else r = m - 1; } } printf("%d\n", ans); } return 0; }
相关文章
- poj2112 二分最大流+Floyd
- 【BZOJ3993】星际战争(网络流,二分答案)
- 【BZOJ2067】[Poi2004]SZN 二分+树上贪心
- 【BZOJ3230】相似子串 后缀数组+二分+RMQ
- 【BZOJ4025】二分图 LCT
- 【BZOJ4554】[Tjoi2016&Heoi2016]游戏 二分图最大匹配
- C#,数据检索算法之二分搜索(Binary Search)的源代码
- 【python】leetcode 704. 二分查找
- CodeForces 671B Robin Hood (二分)
- 二分查找法的C++泛型实现
- 二分查找
- 【bzoj4554】[Tjoi2016&Heoi2016]游戏 二分图最大匹配
- 【bzoj4310】跳蚤 后缀数组+二分