教师资格证查询

题目

1. K13212 教师资格证查询

题目描述

科丁乐的N名老师都考取了信息学教师资格证。科丁乐的数据库中记录了每个老师的教师资格证编号和姓名。教师资格证编号是一个整数，每个老师的教师资格证的编号都是独一无二的。小科想开发一个教师资格证查询系统，输入教师资格证的编号就可以输出对应的老师的姓名。请你帮一帮小科吧。

输入格式

第1行：两个空格分隔的整数N和M，分别表示老师的数量和查询的次数。

接下来N行：每行一个整数d和一个字符串s，分别表示一位老师的教师资格证编号和姓名。

接下来M行：每行一个整数d，表示要查询的教师资格证的编号。

输出格式

共M行：对应M次查询，对于每次查询，如果要查询的教师资格证编号存在，则输出其对应的老师的姓名，如果不存在，输出“error”。

输入输出样例

输入样例1：复制

5 3
1 zhangsan
7 lisi
6 wanger 
3 zhaowu 
5 liuliu 
7 
2 
5

输出样例1：复制

lisi
error 
liuliu 

说明

【数据范围】

1 <=N, M <= 10^5；  1 <= d <= 10^9， 1 <= 姓名s的长度 <= 30；

【耗时限制】1000ms 【内存限制】128MB

解答

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL N=100010;
LL n,m,x;
struct Node{
	LL d;
	string s;
}a[N];
bool cmp(const Node &x,const Node &y){
	return  x.d<y.d;
}
LL Binary_search(Node a[],LL l,LL r,LL x){
	while(l<r){
    	LL mid=(l+r)/2;
    	if(a[mid].d==x) return mid;
    	else if(a[mid].d>x) r=mid;
    	else l=mid+1;
	}
	return -1;
}
int main(){
	cin>>n>>m;
	for(LL i=1;i<=n;i++){
		cin>>a[i].d>>a[i].s;
	}
	sort(a+1,a+n+1,cmp);
	while(m--){
		scanf("%lld",&x);
		LL p=Binary_search(a,1,n+1,x);
		if(p==-1) printf("error\n");
		else cout<<a[p].s<<endl;
	}
	return  0;
}