【九度OJ】题目1069：查找学生信息 解题报告
标签（空格分隔）： 九度OJ
[LeetCode]
http://ac.jobdu.com/problem.php?pid=1069
题目描述：
输入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
Ways
查找题。
按照书上的说法，这个运算量级在千万量级，应该用高速的查找方法。按照书上的说法，应该用二分。
可是我用了sort之后，感觉没必要用二分也能AC，试了下果然行。这个方法应该直接不用sort也能解决。
同时注意一下为什么刚开始一直AC不了，因为我把name和sex的空间开的太小了。这就长个教训，空间给的很足够，只管用就是，别精打细算。
#include <stdio.h>
#include <algorithm>
#include <string.h>
using namespace std;
struct student {
char num[100];
char name[300];
char sex[20];
int age;
bool operator<(const student &A) const {
return strcmp(num, A.num) < 0;
}
} students[1001];
int main() {
int n;
int m;
char temp[1000];
while (scanf("%d", &n) != EOF) {
for (int i = 0; i < n; i++) {
scanf("%s%s%s%d", students[i].num,
students[i].name, students[i].sex, &students[i].age);
}
sort(students, students + n);
scanf("%d", &m);
int j;
for (int i = 0; i < m; i++) {
scanf("%s", temp);
for (j = 0; j < n; j++) {
if (strcmp(temp, students[j].num) == 0) {
printf("%s %s %s %d\n", students[j].num,
students[j].name, students[j].sex, students[j].age);
break;
}
}
if (j == n)
printf("No Answer!\n");
}
}
return 0;
}把上面的方法简化，也能在同样的20ms内解决。而题目的要求是1000ms，差得远呢。所以以后这样的题可以先用笨方法试一试。
#include <stdio.h>
#include <algorithm>
#include <string.h>
using namespace std;
struct student {
char num[100];
char name[300];
char sex[20];
int age;
} students[1001];
int main() {
int n;
int m;
char temp[1000];
while (scanf("%d", &n) != EOF) {
for (int i = 0; i < n; i++) {
scanf("%s%s%s%d", students[i].num, students[i].name, students[i].sex, &students[i].age);
}
scanf("%d", &m);
int j;
for (int i = 0; i < m; i++) {
scanf("%s", temp);
for (j = 0; j < n; j++) {
if (strcmp(temp, students[j].num) == 0) {
printf("%s %s %s %d\n", students[j].num, students[j].name, students[j].sex, students[j].age);
break;
}
}
if (j == n)
printf("No Answer!\n");
}
}
return 0;
}挑战下自己，使用二分进行解决。手写了一下二分，运行时间依然是20ms，感觉很无语。
#include <stdio.h>
#include <algorithm>
#include <string.h>
using namespace std;
struct student {
char num[100];
char name[300];
char sex[20];
int age;
bool operator<(const student &A) const {
return strcmp(num, A.num) < 0;
}
} students[1001];
int main() {
int n;
int m;
char temp[1000];
while (scanf("%d", &n) != EOF) {
for (int i = 0; i < n; i++) {
scanf("%s%s%s%d",
students[i].num, students[i].name,
students[i].sex, &students[i].age);
}
sort(students, students + n);
scanf("%d", &m);
for (int i = 0; i < m; i++) {
scanf("%s", temp);
int start = 0;
int end = n - 1;
int mid;
int answer = -1;
while (start <= end) {
mid = (start + end) / 2;
int cmp = strcmp(temp, students[mid].num);
if (cmp == 0) {
answer = mid;
break;
} else if (cmp < 0) {
end = mid - 1;
} else {
start = mid + 1;
}
}
if (answer == -1) {
printf("No Answer!\n");
} else {
printf("%s %s %s %d\n",
students[answer].num, students[answer].name,
students[answer].sex, students[answer].age);
}
}
}
return 0;
}Date
2017 年 2 月 27 日