3582: 图书馆查询系统 Time Limit(Common/Java):1000MS/3000MS     Memory Limit:65536KByte Total Submit: 779            Accepted:183 Description 台州学院图书馆是一个馆藏丰富、发展迅速的地方性大学图书馆，截止2010年底，图书馆拥有馆藏纸质文献159.7万册。当然图书然必须具备一个图书查询系统，以便同学快速找到某一本书，请编写一个程序实现。 Input 测试数据有多组。 每一组测试数据第一行为一个正整数n(n<=10000)，代表有n本图书； 接下来为n行图书信息： Ai  Bi Ai和Bi 均为长度不大于100的字符串，Ai为书名，例如“c#.net”，Bi为图书的检索号，例如“TP393.08-4312132”，代表了该书存放的位置，n本图书的信息已经根据Ai的字典序排序后输入。 接下来为一个正整数m(m<=10000)，代表查询的次数； 下面的m行，每行为待查询的书名si （si为长度不大于100的字符串）。 Output 对于每一个查询操作，若存在该书目，则输出对应的检索号，否则输出can't find Sample Input
5 algorithm TT6589.965 clock CX951.268 computer  TP21398.123 english TP65.125 math TP98652.369 3 computer algorithm graphics
Sample Output
TP21398.123 TT6589.965 can't find
大致题意：就是给你N本书的名字和编号，在给出M本书的名字，让你在N本书中查找，如果找到了就将这本书的编号输出，如果没有找到 直接输出can't find。
解题思路：常规思路是知道一个名字后就按从前到后的顺序查找，但是这个题目测试数据非常多，采用这种方法一定会超时的，题目中有一句话非常 重要，题中说 n本图书的信息已经根据Ai的字典序排序后输入。也就是图书序列是有序的，对于一个有序的表可以用二分查找。也就是折半查找， 这样查找时速度会快很多。 初始begin=0  end=n-1(查找的范围），mid=(begin+end)/2,   然后用strcmp()字符串比较函数，返回值为0代表当前位置的信息就是要查找的 信息，如果>0说明在前半部分，则end=mid-1，范围缩小了一半，如果<0说明在后半部分，begin=mid+1,当begin>end时查找结束
题目代码： #include<iostream> #include<stdio.h> #include<string.h> #include<stdlib.h> #include<queue> #define max(a,b) a>b?a:b #define INF 0x3f3f3f3f using namespace std; struct infor { char name[102]; char num[102]; }; int main() { int n,m,i,bbegin,mid,eend,flag; char str[102]; infor a[10002]; while(~scanf("%d",&n)) { for(i = 0 ;i < n; i++) scanf("%s%s",a[i].name,a[i].num); //n本书的名字编号 scanf("%d",&m); while(m--) { scanf("%s",str); //m本书的名字，输入一个查找一个 flag = 1;          //代表假设这本书在N本书中是不存在的 bbegin = 0;     //初始查找范围为整个范围 eend = n - 1; while(bbegin <= eend) //只有查找的下届小于或等于上界时才继续 { mid = (bbegin + eend) / 2; //中值坐标 int temp = strcmp(a[mid].name,str);  //当前的字符串，与中间的字符串比较 if(temp == 0)  //为0代表相等，即查到了 { printf("%s\n",a[mid].num);  //输出对应的图书编号 flag = 0; //置为0，代表有解，结束循环 break; } if(temp > 0) //大于0代表中间的字符串比要查的大，则要查的字符串在这个区域的左半部分， { eend = mid - 1; } if(temp < 0) //小于0代表中间的字符串比要查的小，则要查的字符串在这个区域的右半部分 { bbegin = mid + 1; } } if(flag) //循环结束，如果flag无变化说明这本书不存在， printf("can't find\n"); } } return 0; }
3582: 图书馆查询系统 Time Limit(Common/Java):1000MS/3000MS     Memory Limit:65536KByte Total Submit: 779            Accepted:183 Description 台州学院图书馆是一个馆藏丰富、发展迅速的地方性大学图书馆，截止2010年底，图书馆拥有馆藏纸质文献159.7万册。当然图书然必须具备一个图书查询系统，以便同学快速找到某一本书，请编写一个程序实现。 Input 测试数据有多组。 每一组测试数据第一行为一个正整数n(n<=10000)，代表有n本图书； 接下来为n行图书信息： Ai  Bi Ai和Bi 均为长度不大于100的字符串，Ai为书名，例如“c#.net”，Bi为图书的检索号，例如“TP393.08-4312132”，代表了该书存放的位置，n本图书的信息已经根据Ai的字典序排序后输入。 接下来为一个正整数m(m<=10000)，代表查询的次数； 下面的m行，每行为待查询的书名si （si为长度不大于100的字符串）。 Output 对于每一个查询操作，若存在该书目，则输出对应的检索号，否则输出can't find Sample Input
5 algorithm TT6589.965 clock CX951.268 computer  TP21398.123 english TP65.125 math TP98652.369 3 computer algorithm graphics
Sample Output
TP21398.123 TT6589.965 can't find
大致题意：就是给你N本书的名字和编号，在给出M本书的名字，让你在N本书中查找，如果找到了就将这本书的编号输出，如果没有找到 直接输出can't find。
解题思路：常规思路是知道一个名字后就按从前到后的顺序查找，但是这个题目测试数据非常多，采用这种方法一定会超时的，题目中有一句话非常 重要，题中说 n本图书的信息已经根据Ai的字典序排序后输入。也就是图书序列是有序的，对于一个有序的表可以用二分查找。也就是折半查找， 这样查找时速度会快很多。 初始begin=0  end=n-1(查找的范围），mid=(begin+end)/2,   然后用strcmp()字符串比较函数，返回值为0代表当前位置的信息就是要查找的 信息，如果>0说明在前半部分，则end=mid-1，范围缩小了一半，如果<0说明在后半部分，begin=mid+1,当begin>end时查找结束
题目代码： #include<iostream> #include<stdio.h> #include<string.h> #include<stdlib.h> #include<queue> #define max(a,b) a>b?a:b #define INF 0x3f3f3f3f using namespace std; struct infor { char name[102]; char num[102]; }; int main() { int n,m,i,bbegin,mid,eend,flag; char str[102]; infor a[10002]; while(~scanf("%d",&n)) { for(i = 0 ;i < n; i++) scanf("%s%s",a[i].name,a[i].num); //n本书的名字编号 scanf("%d",&m); while(m--) { scanf("%s",str); //m本书的名字，输入一个查找一个 flag = 1;          //代表假设这本书在N本书中是不存在的 bbegin = 0;     //初始查找范围为整个范围 eend = n - 1; while(bbegin <= eend) //只有查找的下届小于或等于上界时才继续 { mid = (bbegin + eend) / 2; //中值坐标 int temp = strcmp(a[mid].name,str);  //当前的字符串，与中间的字符串比较 if(temp == 0)  //为0代表相等，即查到了 { printf("%s\n",a[mid].num);  //输出对应的图书编号 flag = 0; //置为0，代表有解，结束循环 break; } if(temp > 0) //大于0代表中间的字符串比要查的大，则要查的字符串在这个区域的左半部分， { eend = mid - 1; } if(temp < 0) //小于0代表中间的字符串比要查的小，则要查的字符串在这个区域的右半部分 { bbegin = mid + 1; } } if(flag) //循环结束，如果flag无变化说明这本书不存在， printf("can't find\n"); } } return 0; }