首页 购物 网址 三丰软件 | 小说 美女秀 图库大全 游戏 笑话 | 下载 开发知识库 新闻 开发 图片素材
多播视频美女直播
↓电视,电影,美女直播,迅雷资源↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
移动开发 架构设计 编程语言 Web前端 互联网
开发杂谈 系统运维 研发管理 数据库 云计算 Android开发资料
资讯 业界资讯 软件杂谈 编程开发 网站建设 网络观查 搜索引擎 移动应用 网站运营 网络地图
开发 移动开发 Web前端 架构设计 编程语言 互联网 数据库 系统运维 云计算 开发杂谈
[编程语言] 九度1069:查找学生信息(折半||线性查找)
九度1069:查找学生信息(折半||线性查找)

http://ac.jobdu.com/problem.php?pid=1069
题目1069:查找学生信息

时间限制:1 秒
内存限制:32 兆
特殊判题:
提交:7855
解决:2124
题目描述:

 输入N个学生的信息,然后进行查询。
输入:

 输入的第一行为N,即学生的个数(N<=1000)
接下来的N行包括N个学生的信息,信息格式如下:
01 李江 男 21
02 刘唐 男 23
03 张军 男 19
04 王娜 女 19
然后输入一个M(M<=10000),接下来会有M行,代表M次查询,每行输入一个学号,格式如下:
02
03
01
04
输出:

 输出M行,每行包括一个对应于查询的学生的信息。
如果没有对应的学生信息,则输出“No Answer!”
样例输入:
4
01 李江 男 21
02 刘唐 男 23
03 张军 男 19
04 王娜 女 19
5
02
03
01
04
03
样例输出:
02 刘唐 男 23
03 张军 男 19
01 李江 男 21
04 王娜 女 19
03 张军 男 19
来源:
2003年清华大学计算机研究生机试真题
答疑:
解题遇到问题?分享解题心得?讨论本题请访问:http://t.jobdu.com/thread-7793-1-1.html

方法1:直接利用数组线性查找,时间复杂度O(n*m)
方法2:利用折半查找,时间复杂度O(nlogn  (排序) +  m*logn);
//方法1:
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

struct info{
	char number[1010];
	char name[1010];
	char sex[5];
	int age;
}buf[1010];


int main()
{
	int n,m,i,j;
	while(scanf("%d",&n)!=EOF){
		memset(buf,0,sizeof(buf));
		for(i=1;i<=n;i++){
			scanf("%s %s %s %d",buf[i].number,buf[i].name,buf[i].sex,&buf[i].age);
		}
		scanf("%d",&m);
		char x[1010];
		for(i=1;i<=m;i++){
			scanf("%s",x);
			for(j=1;j<=n;j++){
				if(strcmp(x,buf[j].number)==0){
					printf("%s %s %s %d\n",buf[j].number,buf[j].name,buf[j].sex,buf[j].age);
					break;
				}
			}
			if(j==n+1){
				printf("No Answer!\n");
			}
		}
	}
	return 0;
}


//方法2
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

struct Student{
	char no[100];
	char name[100];
	int age;
	char sex[5];
	bool operator < (const Student & A)  const{
		return strcmp(no,A.no)<0;
	}
}buf[1000];

int main()
{
	int n,i;
	while(scanf("%d",&n)!=EOF){
		for(i=0;i<n;i++){
			scanf("%s%s%s%d",buf[i].no,buf[i].name,buf[i].sex,&buf[i].age);
		}
		sort(buf,buf+n);
		int t;
		scanf("%d",&t);
		while(t--!=0){
			int ans=-1;
			char x[30];
			scanf("%s",x);
			int top=n-1,base=0;
			while(top>=base){
				int mid=(top+base)/2;
				int tmp=strcmp(buf[mid].no,x);
				if(tmp==0){
					ans=mid;
					break;
				}
				else if(tmp>0){
					top=mid-1;
				}
				else base=mid+1;
			}
			if(ans==-1){
				printf("No Answer!\n");
			}
			else printf("%s %s %s %d\n",buf[ans].no,buf[ans].name,buf[ans].sex,buf[ans].age);
		}
	}
	return 0;
}



上一篇:python基础
下一篇:LeetCode:Combination Sum

 此文从网络中自动搜索生成,不代表本网站赞成被搜索网站的内容或立场    查看原文
360图书馆 软件开发资料 文字转语音 购物精选 软件下载 新闻资讯 小游戏 Chinese Culture 股票 三丰软件 开发 中国文化 网文精选 阅读网 看图 日历 万年历 2018年12日历
2018-12-13 6:54:57
 
  网站联系 软件世界网-www.sjsjw.com ©2014 蜀ICP备06016416号 三峰网旗下网站