NowCoder 查找学生信息 （二分查找）

本文主要是介绍NowCoder 查找学生信息 （二分查找），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述

输入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!”
示例1

输入

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

solution

二分查找板题，先对结构体重载运算符排序，后二分查找。要熟练运用STL中的二分查找。

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
struct Student
{int id, age;char name[20];char sex[5];bool operator<(Student s){return id < s.id;}
};
Student stu[1001];
int IDs[10001];
int main()
{// freopen("in.txt", "r", stdin);int N;char ch[10];while (scanf("%d", &N) != EOF){for (int i = 0; i < N; i++)scanf("%d %s %s %d", &stu[i].id, stu[i].name, stu[i].sex, &stu[i].age);int M;scanf("%d", &M);for (int i = 0; i < M; i++)scanf("%d", &IDs[i]);// 排序sort(stu, stu + N);/*STL中二分算法的python实现，返回不小于value的下标def lower_bound(array, first, last, value): # 返回[first, last)内第一个不小于value的值的位置while first < last: # 搜索区间[first, last)不为空mid = first + (last - first) // 2  # 防溢出if array[mid] < value: first = mid + 1else:last = midreturn first  # last也行，因为[first, last)为空的时候它们重合*/for (int i = 0; i < M; i++){int value = IDs[i], first = 0, last = N, mid;while (first < last){mid = first + (last - first) / 2;if (stu[mid].id < value)first = mid + 1;elselast = mid;}if (stu[first].id == value){printf("%d %s %s %d\n", stu[first].id, stu[first].name, stu[first].sex, stu[first].age);}elseprintf("No Answer!\n");}}return 0;
}

这篇关于NowCoder 查找学生信息 （二分查找）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---