📖 第 3.8 章 ⏱️ 约 55 分钟 🎯 中级

第 3.8 章：映射与集合

映射和集合是频率统计、查找和跟踪唯一元素的主力工具。本章深入探讨它们在 USACO 题目中的实际应用。

📝 前置条件： 熟悉数组和基础 C++ STL（第 2.4 章）。了解哈希表概念（第 3.7 章）有帮助，但不是严格要求——map 和 set 基于树结构，不依赖哈希。

3.8.1 map vs unordered_map —— 明智地选择

图示：Map 内部结构（BST）

Map Structure

std::map 将键值对存储在平衡 BST（红黑树）中，所有操作 O(log N) 且键自动有序——当你需要 lower_bound/upper_bound 查询时非常有用。只需 O(1) 查找且不需要顺序时，用 unordered_map。

map 和 unordered_map 的关键结构差异：

map vs unordered_map

特性mapunordered_map
底层结构红黑树哈希表
插入/查找时间O(log n)平均 O(1)，最坏 O(n)
遍历顺序按键有序任意顺序
最小/最大键通过 .begin()/.rbegin() 获取不支持
键的要求可比较（有 <）可哈希
使用场景需要有序键或最大最小键时需要最快查找时

大多数 USACO 题目两者都能用。键是整数或字符串时用 unordered_map 求速度，需要有序遍历时用 map。

示例：频率映射

📄 查看代码：示例：频率映射 
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    unordered_map<int, int> freq;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        freq[x]++;   // 计数加一；若不存在则以 0 创建
    }

    // 找出现频率最高的元素
    int maxFreq = 0, maxVal = INT_MIN;
    for (auto &[val, count] : freq) {   // 结构化绑定（C++17）
        if (count > maxFreq || (count == maxFreq && val < maxVal)) {
            maxFreq = count;
            maxVal = val;
        }
    }

    cout << "最频繁：" << maxVal << "（" << maxFreq << " 次）\n";

    return 0;
}

3.8.2 Map 操作——完整参考

📄 查看代码：3.8.2 Map 操作——完整参考 
#include <bits/stdc++.h>
using namespace std;

int main() {
    map<string, int> scores;

    // 插入
    scores["Alice"] = 95;
    scores["Bob"] = 87;
    scores["Charlie"] = 92;
    scores.insert({"Dave", 78});    // 另一种方式
    scores.emplace("Eve", 88);      // 最高效的方式

    // 查找
    cout << scores["Alice"] << "\n";  // 95
    // 警告：scores["Unknown"] 会以值 0 创建该项！

    // 安全查找
    if (scores.count("Frank")) {
        cout << scores["Frank"] << "\n";
    } else {
        cout << "Frank not found\n";
    }

    // 使用 find() — 返回迭代器
    auto it = scores.find("Bob");
    if (it != scores.end()) {
        cout << it->first << ": " << it->second << "\n";  // Bob: 87
    }

    // 更新
    scores["Alice"] += 5;    // Alice 现在是 100

    // 删除
    scores.erase("Charlie");

    // 按键有序遍历（map 始终保证有序）
    for (const auto &[name, score] : scores) {
        cout << name << ": " << score << "\n";
    }
    // Alice: 100
    // Bob: 87
    // Dave: 78
    // Eve: 88

    // 大小和空检查
    cout << scores.size() << "\n";   // 4
    cout << scores.empty() << "\n";  // 0（假）

    // 清空所有条目
    scores.clear();

    return 0;
}

3.8.3 Set 操作——完整参考

📄 查看代码：3.8.3 Set 操作——完整参考 
#include <bits/stdc++.h>
using namespace std;

int main() {
    set<int> s = {5, 3, 8, 1, 9, 2};
    // s = {1, 2, 3, 5, 8, 9}（始终有序！）

    // 插入
    s.insert(4);   // s = {1, 2, 3, 4, 5, 8, 9}
    s.insert(3);   // 已存在，无变化

    // 删除
    s.erase(8);    // s = {1, 2, 3, 4, 5, 9}

    // 查找
    cout << s.count(3) << "\n";  // 1（存在）
    cout << s.count(7) << "\n";  // 0（未找到）

    // 基于迭代器的查询
    auto it = s.lower_bound(4);  // 第一个 >= 4 的元素
    cout << *it << "\n";         // 4

    auto it2 = s.upper_bound(4); // 第一个 > 4 的元素
    cout << *it2 << "\n";        // 5

    // 最小值和最大值
    cout << *s.begin() << "\n";   // 1（最小）
    cout << *s.rbegin() << "\n";  // 9（最大）

    // 移除最小值
    s.erase(s.begin());   // 移除 1
    cout << *s.begin() << "\n";  // 2

    // 遍历
    for (int x : s) cout << x << " ";
    cout << "\n";  // 2 3 4 5 9

    return 0;
}

3.8.4 USACO 题目：奶牛 ID

题目（USACO 2017 February Bronze）： 给定一组「已占用」的 ID 集合和 N，找第 N 个可用的 ID。

📄 C++ 完整代码 
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, q;
    cin >> n >> q;

    set<int> taken;
    for (int i = 0; i < n; i++) {
        int x; cin >> x;
        taken.insert(x);
    }

    // 对每个查询 q，找第 q 个不在 taken 中的正整数
    while (q--) {
        int k; cin >> k;

        // 二分查找：找最小的 x 使得 x - (x 以内已占用的数量) >= k
        int lo = 1, hi = 2e9;
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            // [1, mid] 中可用数量 = mid - (≤ mid 的已占用数量)
            int taken_count = (int)(taken.lower_bound(mid + 1) - taken.begin());
            int available = mid - taken_count;
            if (available >= k) hi = mid;
            else lo = mid + 1;
        }

        cout << lo << "\n";
    }

    return 0;
}

3.8.5 Multiset——允许重复的有序集合

multiset 类似于 set，但允许重复值：

📄 `multiset` 类似于 set，但允许重复值： 
#include <bits/stdc++.h>
using namespace std;

int main() {
    multiset<int> ms;
    ms.insert(3);
    ms.insert(1);
    ms.insert(3);   // 允许重复
    ms.insert(5);
    ms.insert(1);

    // ms = {1, 1, 3, 3, 5}

    cout << ms.count(3) << "\n";  // 2（有几个 3）
    cout << ms.count(2) << "\n";  // 0

    // 只移除一个 3
    ms.erase(ms.find(3));  // 只移除一个 3
    // ms = {1, 1, 3, 5}

    // 移除所有的 1
    ms.erase(1);  // 移除所有 1
    // ms = {3, 5}

    cout << *ms.begin() << "\n";   // 3（最小）
    cout << *ms.rbegin() << "\n";  // 5（最大）

    return 0;
}

用两个 Multiset 维护动态中位数

用最大 multiset（下半部分）和最小 multiset（上半部分）跟踪数据流的中位数：

📄 用最大 multiset（下半部分）和最小 multiset（上半部分）跟踪数据流的中位数： 
#include <bits/stdc++.h>
using namespace std;

int main() {
    multiset<int> lo;  // 下半部分（rbegin() = 最大值）
    multiset<int> hi;  // 上半部分（begin() = 最小值）

    int n;
    cin >> n;

    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;

        // 加入合适的半部分
        if (lo.empty() || x <= *lo.rbegin()) {
            lo.insert(x);
        } else {
            hi.insert(x);
        }

        // 重新平衡：大小差不超过 1
        while (lo.size() > hi.size() + 1) {
            hi.insert(*lo.rbegin());
            lo.erase(lo.find(*lo.rbegin()));
        }
        while (hi.size() > lo.size()) {
            lo.insert(*hi.begin());
            hi.erase(hi.begin());
        }

        // 打印中位数
        if (lo.size() == hi.size()) {
            // 偶数个：两个中间值的平均
            double median = (*lo.rbegin() + *hi.begin()) / 2.0;
            cout << fixed << setprecision(1) << median << "\n";
        } else {
            // 奇数个：中间值在 lo 中
            cout << *lo.rbegin() << "\n";
        }
    }

    return 0;
}

3.8.6 实用模式

模式一：统计不同元素

vector<int> data = {1, 5, 3, 1, 2, 5, 5, 3};
set<int> distinct(data.begin(), data.end());
cout << "不同值的个数：" << distinct.size() << "\n";  // 4

模式二：按频率分组，按值排序

📄 查看代码：模式二：按频率分组，按值排序 
vector<int> nums = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5};
map<int, int> freq;
for (int x : nums) freq[x]++;

// 按频率分组
map<int, vector<int>> byFreq;
for (auto &[val, cnt] : freq) {
    byFreq[cnt].push_back(val);
}

// 按频率顺序打印
for (auto &[cnt, vals] : byFreq) {
    for (int v : vals) cout << v << "（×" << cnt << "）\n";
}

模式三：离线查询与排序结合

将查询与事件一起排序，以 O((N+Q) log N) 一起处理：

// 示例：对每个查询点，统计有多少事件的值 <= 查询点
// 对两个数组排序，用双指针扫描

⚠️ 第 3.8 章常见错误

#错误错在哪里修复方法
1map[key] 访问不存在的键自动创建值为 0 的条目，污染数据先用 m.count(key) 或 m.find(key) 检查
2multiset::erase(value) 删除所有相等值本想删一个，却删光了用 ms.erase(ms.find(value)) 只删一个
3遍历时修改 map/set 大小迭代器失效，崩溃或跳过元素用 it = m.erase(it) 安全删除
4unordered_map 被 hack 退化到 O(N)攻击者构造哈希碰撞数据，TLE换用 map 或使用自定义哈希函数
5忘记 set 不存储重复值插入重复后 size() 不增，计数出错需要重复时用 multiset

本章总结

📌 核心要点

结构有序？允许重复？关键特性为什么重要
map<K,V>是（有序）否（唯一键）键值映射，O(log N)频率统计、ID→属性映射
unordered_map<K,V>否否平均 O(1) 查找大数据下比 map 快 5-10 倍
set<T>是（有序）否有序唯一集合去重，范围查询（lower_bound）
unordered_set<T>否否O(1) 成员检测只需检查「是否见过」
multiset<T>是（有序）是有序多集合动态中位数、滑动窗口

🧩 「用哪个容器」速查

需求推荐容器原因
统计每个元素出现次数map / unordered_map一行 freq[x]++
去重并排序set自动去重 + 自动排序
检查元素是否已见unordered_setO(1) 查找
动态有序集合 + 求极值set / multisetO(1) 访问最小/最大值
需要 lower_bound / upper_boundset / map只有有序容器支持
值→下标映射map / unordered_map坐标压缩等场景

❓ 常见问题

Q1：map 的 [] 运算符和 find 有什么区别？

A：m[key] 当键不存在时会自动创建默认值（int 的默认值为 0）；m.find(key) 只查找，不创建。如果只想检查键是否存在，用 m.count(key) 或 m.find(key) != m.end()。

Q2：multiset 和 priority_queue 都能取极值——用哪个？

A：priority_queue 只能取极值并删除，不支持按值删除。multiset 支持查找并删除任意值，更灵活。只需反复取极值时，priority_queue 更简单；需要删除特定元素（如滑动窗口移除离开的元素）时，用 multiset。

Q3：unordered_map 什么时候比 map 慢？

A：两种情况：① 哈希碰撞严重时（多个键哈希到同一桶），退化到 O(N)；② 竞赛中攻击者故意构造数据 hack unordered_map。解决方案：使用自定义哈希函数，或切换到 map。

Q4：C++17 结构化绑定 auto &[key, val] 安全吗？竞赛中能用吗？

A：USACO 和大多数竞赛平台支持 C++17，for (auto &[key, val] : m) 可以安全使用。比 entry.first/entry.second 更简洁。

🔗 与后续章节的联系

  • 第 3.3 章（排序与搜索）：坐标压缩常与 map 结合（值 → 压缩后下标）
  • 第 3.9 章（线段树）：有序 set 的 lower_bound 可以替代简单的线段树查询
  • 第 5.1–5.2 章（图）：map 常用于存储稀疏图的邻接表
  • 第 4.1 章（贪心）：multiset 结合贪心策略可以高效维护动态最优选择
  • map 频率统计模式贯穿全书，是竞赛编程中最基础的工具之一

练习题

题目 3.8.1 — 两数之和 🟢 简单 读取 N 个整数和目标 T，找两个相加等于 T 的值，打印它们的下标（1-indexed）。

✅ 完整题解 
#include <bits/stdc++.h>
using namespace std;
int main() {
    int n, T; cin >> n >> T;
    map<int, int> seen;  // 值 → 下标
    for (int i = 1; i <= n; i++) {
        int x; cin >> x;
        if (seen.count(T - x)) {
            cout << seen[T - x] << " " << i << "\n";
            return 0;
        }
        seen[x] = i;
    }
    cout << "no solution\n";
}

复杂度： 用 map O(N log N)，用 unordered_map O(N)。

题目 3.8.2 — 字母异位词分组 🟡 中等 将 N 个单词按其字母排序后的形式分组。

✅ 完整题解 
#include <bits/stdc++.h>
using namespace std;
int main() {
    int n; cin >> n;
    map<string, vector<string>> groups;
    for (int i = 0; i < n; i++) {
        string w; cin >> w;
        string key = w; sort(key.begin(), key.end());
        groups[key].push_back(w);
    }
    for (auto& [key, words] : groups) {
        sort(words.begin(), words.end());
        for (const string& w : words) cout << w << " ";
        cout << "\n";
    }
}

复杂度： O(N × K log K)，K = 平均单词长度。

题目 3.8.3 — 区间最大重叠数 🟡 中等 统计 N 个区间在点 1..M 上的最大重叠数。

✅ 完整题解 
#include <bits/stdc++.h>
using namespace std;
int main() {
    int n, M; cin >> n >> M;
    vector<int> diff(M + 2, 0);
    for (int i = 0; i < n; i++) {
        int l, r; cin >> l >> r;
        diff[l]++; diff[r+1]--;
    }
    int cur = 0, ans = 0;
    for (int i = 1; i <= M; i++) {
        cur += diff[i];
        ans = max(ans, cur);
    }
    cout << ans << "\n";
}

复杂度： O(N + M)。

题目 3.8.4 — 奶牛摄影 🔴 困难 找与所有 N 个列表（每个都是 ID 的一个排列）一致的顺序。

✅ 完整题解

核心思路： 对每对 (a, b)，统计 a 在多少个列表中排在 b 之前。若 a 在超过一半的列表中排在 b 前面，则 a 在真实顺序中排在 b 前面。用这个成对比较来排序。

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n, k; cin >> n >> k;
    vector<vector<int>> pos(k, vector<int>(n+1));
    for (int i = 0; i < k; i++)
        for (int j = 0; j < n; j++) {
            int x; cin >> x; pos[i][x] = j;
        }
    vector<int> cows(n); iota(cows.begin(), cows.end(), 1);
    sort(cows.begin(), cows.end(), [&](int a, int b){
        int before = 0;
        for (int i = 0; i < k; i++) before += (pos[i][a] < pos[i][b]);
        return before > k / 2;
    });
    for (int c : cows) cout << c << "\n";
}

题目 3.8.5 — 实时不同值计数 🟢 简单 每读入一个新整数后，打印到目前为止见过的不同值的个数。

✅ 完整题解 
#include <bits/stdc++.h>
using namespace std;
int main() {
    int n; cin >> n;
    unordered_set<int> seen;
    for (int i = 0; i < n; i++) {
        int x; cin >> x;
        seen.insert(x);
        cout << seen.size() << "\n";
    }
}

复杂度： O(N) 均摊。