算法日记 | STL-MAP
🚀C++ 刷题日记：Map 的三种“打开方式”，从入门到超时再到 AC！
🚀 导语
在算法竞赛和日常开发中，std::map绝对是 C++ STL 里的“万金油”。它不仅能自动排序，还能提供极快的键值对查找能力。
最近我刷到了三道关于map的经典题目，涵盖了基础增删改查、反向映射优化以及数学逻辑转换。今天就把我的解题思路、踩过的坑以及最终的 AC 代码整理出来，分享给大家！
🟢 第一题：P5266【深基17.例6】学籍管理
📝 题目描述
您需要设计一个学籍管理系统，最开始时数据都是空的。然后该系统能够支持下面的操作（不超过10510^5105条）：
- 输入与修改，格式
1 NAME SCORE：在系统中插入姓名为 NAME(由字母和数字组成不超过 20 个字符的字符串，区分大小写)，分数为 SCORE (0≤SCORE<2310 \le \text{SCORE} < 2^{31}0≤SCORE<231) 的学生。如果已经有同名的学生则更新该学生的成绩为 SCORE。如果成功插入或者修改则输出OK。 - 查询，格式
2 NAME：在系统中查询姓名为 NAME 的学生成绩。如果没找到这名学生则输出Not found，否则输出该生成绩。 - 删除，格式
3 NAME：在系统中删除姓名为 NAME 的学生信息。如果没能找到这名学生则输出Not found，否则输出Deleted successfully。 - 汇总，格式
4：输出系统中学生数量。
输入格式
第一行，输入一个正整数 Q (1≤Q≤1051 \le Q \le 10^51≤Q≤105)，表示操作数量。
接下来 Q 行，每行先输入一个正整数 op (op∈[1,4]op \in [1, 4]op∈[1,4])，表示操作种类。接着：
- 如果 op = 1，则再输入一个字符串 NAME 以及一个正整数 SCORE，含义见题目描述。
- 如果 op = 2，则再输入一个字符串 NAME，含义见题目描述。
- 如果 op = 3，则再输入一个字符串 NAME，含义见题目描述。
- 如果 op = 4，则无需再输入其他内容。
输出格式
共输出 Q 行，每行输出一个字符串或正整数，为对应操作的处理结果，具体含义见题目描述。
💡 解题思路
这道题是map的教科书级应用。
- 核心数据结构：使用
map<string, long long>，其中string存姓名（Key），long long存分数（Value）。 - 插入与更新：
map的下标操作符[]非常强大。mp[name] = score;这行代码会自动判断：如果name存在，就覆盖旧值；如果不存在，就新建键值对。 - 查询与删除：利用
mp.count(name)来检查键是否存在，避免直接访问不存在的键导致意外插入默认值。
💻 AC 代码实现
#include<bits/stdc++.h>usingnamespacestd;intmain(){// 开启快速IO，防止大数据量下输入输出超时ios::sync_with_stdio(false);cin.tie(0);longlongn;cin>>n;map<string,longlong>mp;while(n--){longlongop;cin>>op;if(op==1){string name;longlongscore;cin>>name>>score;// map的下标操作符可以直接赋值，存在则更新，不存在则插入mp[name]=score;cout<<"OK"<<endl;}elseif(op==2){string name;cin>>name;// count()返回键出现的次数，map中只能是0或1if(mp.count(name))cout<<mp[name]<<endl;elsecout<<"Not found"<<endl;}elseif(op==3){string name;cin>>name;if(mp.count(name)){mp.erase(name);// 删除操作cout<<"Deleted successfully"<<endl;}elsecout<<"Not found"<<endl;}else{// op == 4cout<<mp.size()<<endl;// size()直接获取元素个数}}return0;}🟡 第二题：P1918 保龄球
📝 题目描述
DL 算得分算得很烦闷，所以常常到体育馆去打保龄球解闷。因为他保龄球已经打了几十年了，所以技术上不成问题，于是他就想玩点新花招。
DL 的眼力真的很不错，虽然能够数清楚在他前方十米左右每个位置的瓶子的数量。他突然发现这是一个炫耀自己眼力的好借口——他看清远方瓶子的个数后从某个位置发球，这样就能打到一定数量的瓶子。
- ○○○
- ○○○○
- ○
- ○○○
如上，每个 “○” 代表一个瓶子。如果 DL 想要打到 3 个瓶子就在 1 位置发球，想要打到 4 个瓶子就在 2 位置发球。
现在他想打倒 m 个瓶子。他告诉你每个位置的瓶子数，请你给他一个发球位置。
输入格式
第一行包含一个正整数 n，表示位置数。
第二行包含 n 个正整数aia_iai，表示 i 个位置的瓶子数，保证各个位置的瓶子数不同。
第三行包含一个正整数 Q，表示 DL 发球的次数。
第四行至文件尾，每行包含一个正整数 m，表示 DL 想要打倒 m 个瓶子。
输出格式
共 Q 行。第 i 行的整数表示 DL 第 i 次的发球位置。若无解，则输出 0。
💡 解题思路与“踩坑”实录
这道题乍一看很简单，但很容易掉进陷阱！
❌错误示范（暴力枚举 - TLE）
刚开始我的想法很直接：把数据存进 map 里，每次查询时，遍历整个 map，看看哪个值的瓶子数等于目标 m。代码如下：
// ❌ 错误代码：时间复杂度 O(M*N)，会超时！for(autoit=mp.begin();it!=mp.end();it++){if(it->second==x){// 遍历查找值k=it->first;}}为什么超时？
因为 map 是基于 Key 排序的，查找 Value 必须遍历所有元素。当N,MN, MN,M达到10510^5105级别时，运算量高达101010^{10}1010，计算机根本跑不完。
✅正确思路（反向映射）
我们需要利用 mapKey 查找快的特性。既然我们要通过“瓶子数”找“位置”，那就把瓶子数作为 Key，位置作为 Value！
这样，查询时直接用mp[x]，时间复杂度瞬间降为O(logN)O(\log N)O(logN)。
💻 AC 代码实现
#include<bits/stdc++.h>usingnamespacestd;intmain(){ios::sync_with_stdio(false);cin.tie(0);longlongn;cin>>n;// 核心技巧：反向映射！Key存瓶子数，Value存位置编号map<longlong,longlong>mp;for(longlongi=1;i<=n;i++){longlongnum;cin>>num;mp[num]=i;// 瓶子数是Key，位置是Value}longlongm;cin>>m;for(inti=0;i<m;i++){longlongx;cin>>x;// 直接通过 Key 查找，O(logN) 复杂度if(mp.count(x))cout<<mp[x]<<endl;elsecout<<0<<endl;}return0;}🔴 第三题：P1102 A-B 数对
📝 题目背景
出题是一件痛苦的事情！
相同的题目看多了也会有审美疲劳，于是我舍弃了大家所熟悉的 A+B Problem，改用 A-B 了哈哈！
题目描述
给出一串正整数数列以及一个正整数 C，要求计算出所有满足A−B=CA - B = CA−B=C的数对的个数（不同位置的数字一样的数对算不同的数对）。
输入格式
输入共两行。
第一行，两个正整数 N, C。
第二行，第 i 个数为aia_iai，数字之间用一个空格隔开，共 N 个正整数，作为要求处理的那串数。
输出格式
一行，表示该串正整数中包含的满足A−B=CA - B = CA−B=C的数对的个数。
输入输出样例
| 输入 #1 | 输出 #1 |
|---|---|
| 4 11 1 2 3 | 3 |
说明/提示
对于 75% 的数据，1≤N≤20001 \le N \le 20001≤N≤2000。
对于 100% 的数据，1≤N≤2×1051 \le N \le 2 \times 10^51≤N≤2×105，0≤ai<2300 \le a_i < 2^{30}0≤ai<230，1≤C<2301 \le C < 2^{30}1≤C<230。
💡 解题思路
这道题考察的是数学公式变形 + Map 计数。
如果暴力双重循环查找A−B=CA - B = CA−B=C，复杂度是O(N2)O(N^2)O(N2)，对于N=2×105N=2 \times 10^5N=2×105的数据肯定超时。
我们可以把公式变形为：A=B+CA = B + CA=B+C。
这意味着，对于数组中的每一个数BBB（我们把它当作减数），我们只需要知道数组里有多少个AAA等于B+CB + CB+C即可。
- 预处理：先遍历一遍数组，用
map<int, long long>统计每个数字出现的次数。这里 Value 必须是long long，因为答案可能很大。 - 统计答案：再次遍历数组，对于每个数a[i]a[i]a[i]，计算目标值
target = a[i] + C，然后直接在 map 中查找target出现的次数，累加到答案中。
💻 AC 代码实现
#include<bits/stdc++.h>usingnamespacestd;intmain(){ios::sync_with_stdio(false);cin.tie(0);intn,c;cin>>n>>c;vector<int>a(n);// 使用 map 记录每个数字出现的次数// 注意：次数可能会很多，累加后需要用 long longmap<int,longlong>cnt;for(inti=0;i<n;i++){cin>>a[i];cnt[a[i]]++;// 计数加 1}longlongans=0;for(inti=0;i<n;i++){// 寻找满足 A - B = C 的 A，即 A = B + C// 当前 a[i] 是 B，我们要找值为 a[i] + c 的 A 有多少个inttarget=a[i]+c;ans+=cnt[target];}cout<<ans;return0;}🌟 总结
通过这三道题，我们可以看到std::map的强大之处：
- 基础应用：它是天然的字典，适合处理字符串映射、模拟管理系统。
- 性能优化：通过反向映射（交换 Key 和 Value），可以将暴力查找转化为高效的二分查找。
- 算法辅助：结合数学公式变形，可以将O(N2)O(N^2)O(N2)的问题优化为O(NlogN)O(N \log N)O(NlogN)。
希望这篇推文能帮你更好地理解 Map 的用法！如果你觉得有用，欢迎点赞、在看、转发三连支持一下！❤️