P5266 【深基17.例6】学籍管理

算法题思路分享

题目描述

您要设计一个学籍管理系统，最开始学籍数据是空的，然后该系统能够支持下面的操作（不超过10 5 10^5105条）：

• 插入与修改，格式1 NAME SCORE：在系统中插入姓名为NAME \texttt{NAME}NAME(由字母和数字组成不超过20 2020个字符的字符串，区分大小写)，分数为SCORE \texttt{SCORE}SCORE（0 < SCORE < 2 31 0<\texttt{SCORE}<2^{31}0<SCORE<231） 的学生。如果已经有同名的学生则更新这名学生的成绩为SCORE \texttt{SCORE}SCORE。如果成功插入或者修改则输出OK。
• 查询，格式2 NAME：在系统中查询姓名为NAME \texttt{NAME}NAME的学生的成绩。如果没能找到这名学生则输出Not found，否则输出该生成绩。
• 删除，格式3 NAME：在系统中删除姓名为NAME \texttt{NAME}NAME的学生信息。如果没能找到这名学生则输出Not found，否则输出Deleted successfully。
• 汇总，格式4：输出系统中学生数量。

输入格式

第一行，输入一个正整数Q QQ（1 ≤ Q ≤ 10 5 1 \le Q \le 10^51≤Q≤105），表示操作数量。

接下来Q QQ行，每行先输入一个正整数o p opop（o p ∈ [ 1 , 4 ] op \in [1,4]op∈[1,4]），表示操作种类。接着：

• 如果o p = 1 op = 1op=1，则再输入一个字符串NAME \texttt{NAME}NAME以及一个正整数SCORE \texttt{SCORE}SCORE，含义见题目描述。
• 如果o p = 2 op = 2op=2，则再输入一个字符串NAME \texttt{NAME}NAME，含义见题目描述。
• 如果o p = 3 op = 3op=3，则再输入一个字符串NAME \texttt{NAME}NAME，含义见题目描述。
• 如果o p = 4 op = 4op=4，则无需再输入其他内容。

输出格式

共输出Q QQ行，每行输出一个字符串或正整数，为对应操作的处理结果，具体含义见题目描述。

输入输出样例 #1

输入 #1

5 1 lxl 10 2 lxl 3 lxl 2 lxl 4

输出 #1

OK 10 Deleted successfully Not found 0

解题思路

1. 这个题目非常常规且简单的模拟题，使用map这个STL就能实现增删改查。因此顺着题目意思写代码即可。完整代码如下：

// P5266 【深基17.例6】学籍管理// 用 map 做键值映射，键为姓名，值为分数#include<bits/stdc++.h>usingnamespacestd;intmain(){// 操作条数intq;cin>>q;// 姓名 -> 分数，底层是平衡树，单次查找 O(log n)map<string,int>mp;while(q--){// 本次操作的类型intop;cin>>op;// 1 录入 2 查询 3 删除 4 统计人数if(op==1){// 读入姓名与分数string s;intscore;cin>>s>>score;// operator[] 本身就能插入或覆盖，同名以最新分数为准mp[s]=score;cout<<"OK"<<'\n';}if(op==2){// 按姓名查找string s;cin>>s;autoit=mp.find(s);if(it!=mp.end()){// 命中，second 即对应分数cout<<it->second<<'\n';}else{// 未命中，表里没有这条记录cout<<"Not found"<<'\n';}}if(op==3){// 按姓名删除string s;cin>>s;autoit=mp.find(s);if(it!=mp.end()){// 迭代器已经拿到，直接 erase，省一次按键查找mp.erase(it);cout<<"Deleted successfully"<<'\n';}else{// 记录不存在，自然删不掉cout<<"Not found"<<'\n';}}if(op==4){// 当前记录条数cout<<mp.size()<<'\n';}}return0;}