C++ map容器在算法竞赛中的高效应用与优化

1. 课程背景与核心价值

卡码网的C++基础课是一套面向算法竞赛和编程面试的语法速成教程。作为一名经历过校招和算法竞赛的老手，我深刻理解新手在刷题时面临的困境——很多同学不是被算法思路难住，而是被基础的语法细节绊倒。这套课程的价值就在于它精准切中了这个痛点。

课程采用"语法点+实战题目"的双轨制设计，每个知识点都配有对应的编程题。比如"开房门"这道题，表面看是简单的输入输出练习，实际上暗藏了map容器的使用技巧。这种设计让学习者在解决实际问题的过程中自然掌握语法，比单纯看理论文档高效得多。

提示：虽然课程标价66元，但部分章节（如链表操作、开房门等）提供免费试看，建议先体验再决定是否购买完整版。

2. "开房门"题目解析

2.1 题目场景还原

题目描述大致是这样的：给定n个房客的姓名和房间号，接着输入m次查询，每次查询一个姓名，要求输出对应的房间号。如果查无此人，则返回"Not Found"。

这实际上是一个典型的键值对查询问题，考察的是如何高效实现姓名到房间号的映射。在C++中，最合适的工具就是STL中的map容器。

2.2 输入输出样例

假设输入为：

code复制3
Alice 101
Bob 202
Charlie 303
2
Alice
David

则正确输出应为：

code复制101
Not Found

3. map容器深度剖析

3.1 为什么选择map而不是数组？

初学者可能会想用两个数组分别存储姓名和房间号，然后线性查找。这种方法在n很小时可行，但当n达到1e5量级时，O(n)的查询效率会直接导致超时。而map基于红黑树实现，查询时间复杂度是O(log n)，可以轻松处理大规模数据。

3.2 map的基本操作

cpp复制#include <map>
#include <string>

std::map<std::string, int> roomMap;  // 键是string类型，值是int类型

// 插入元素
roomMap["Alice"] = 101;  
// 或者用insert
roomMap.insert({"Bob", 202});

// 查询元素
if (roomMap.find("Alice") != roomMap.end()) {