C++中的哈希（map,unordered_map)
一：map，unordered_map本质区别
二：底层原理区别
三：简单暴力理解
哈希题目
1.优质数对（蓝桥云课）
题目
https://www.lanqiao.cn/problems/3877/learning/?page=1&first_category_id=1&name=%E4%BC%98%E8%B4%A8%E6%95%B0%E5%AF%B9
分析：
用哈希表unordered_map
关键：
ai==bj;
bi==aj;
ai*sb+bi==bj*sb+aj;sb必须大于ai,bi该等式唯一成立
哈希循环部分先查找后插入
代码
2.字符串统计
题目
https://www.lanqiao.cn/problems/1206/learning/?page=1&first_category_id=1&name=%E5%AD%97%E7%AC%A6%E4%B8%B2%E7%BB%9F%E8%AE%A1
分析
较简单，直接看注释
代码
3.字符统计（蓝桥杯2022省赛）
题目
https://www.lanqiao.cn/problems/2142/learning/?page=1&first_category_id=1&name=%E5%AD%97%E7%AC%A6%E7%BB%9F%E8%AE%A1
分析
用map:最后输出按字母顺序（ABCD）
以字符为key字符个数为value建立哈希表
auto x : h：遍历哈希表（后面解释）
代码
4.训练士兵（蓝桥杯2024省赛）
题目
https://www.lanqiao.cn/problems/19703/learning/?page=1&first_category_id=1&name=%E8%AE%AD%E7%BB%83%E5%A3%AB%E5%85%B5
分析
- 团购：花 S 金币，所有还没练满的士兵都练一次。
- 单买：第 i 个士兵练一次花 pi 金币。
贪心策略：当所有还没练满的士兵单买一次的总花费（即 onesum）大于团购价 S 时，我们就一直进行团购。直到剩下的士兵太少了，单买比团购更便宜，我们才停止团购，转为全部单买。
代码中使用了 std::map<long long, long long> m，这里的哈希（严格说是红黑树实现的有序映射）起到了两个关键作用：
- 归类：把需要训练次数相同的士兵放在一起。it->first 是需要训练的次数 ci，it->second 是这些士兵单买一次的总花费。
- 排序：map 会自动按训练次数 ci 从小到大排序。这非常重要，因为训练次数少的士兵会先 “毕业”，他们一旦练满，就不再贡献单买的费用了。
3. 代码执行逻辑
初始化：先假设所有士兵全部单买（计算出总额 sum），并算出第一轮所有人单买一次的总价 onesum。
贪心筛选：
- 遍历 map（按照训练次数从小到大）。
- 只要当前的 onesum > S（团购更划算），我们就把这一批士兵 “团购” 到毕业。
- 更新状态：每当一批训练次数少的士兵练满了，就把他们单买一次的钱从 onesum 里扣掉，因为以后团购不需要考虑他们了。
计算差价：
- 通过公式 sum = sum + temp * s – onesum * temp; 修正总花费。
- 这步本质是：加上团购花的钱，减去原本计算单买时多算的钱。
利用 map 的有序性，从训练次数最少的士兵开始剔除，动态维护“当前单买一次的总成本”，非常高效。
for(auto p : h)的解释
用于遍历哈希表
加&,若p.seconf值改变，哈希数组mp也会变（理解为操作本身
