当前没有测试数据。

map容器 & 二进制枚举 课堂笔记

一、课前基础铺垫

1. 容器核心概念

C++容器是用于存储/管理数据的工具，本节课涉及两类核心容器：

• vector：动态数组，大小可动态调整（本节课未实战，仅作为对比）
• map：键值对容器，可存储“键-值”对应关系（如姓名→学号）
• queue：队列容器（本节课仅声明未使用，暂不展开）

2. 进制转换基础（二进制枚举前置知识）

• 十进制转二进制：除2取余，逆序排列（不足指定位数补前导0）
• 二进制枚举核心：用十进制数的二进制表示“选/不选”状态（1=选，0=不选）

二、二进制枚举（解决组合/分组问题）

1. 核心用途

解决“从n个元素中选若干个”的组合问题（如：将数组分成两组，求两组和的最小差值）

2. 核心函数：tento(int x)（十进制转n位二进制字符串）

string tento(int x){
    if (x == 0) return "0"; // 处理x=0的特殊情况
    string ans =  "";
    while (x > 0){
        int ys = x % 2; // 取余数（0/1）
        ans = char(ys +  '0') + ans; // 拼接二进制位（逆序拼接）
        x /= 2; // 整除2，缩小x
    }
    while (ans.size() < n) ans = "0" + ans; // 补前导0，保证长度为n
    return ans;
}

• 输入：十进制数x（如x=13）
• 输出：n位二进制字符串（如n=5时，输出"01101"）
• 作用：将枚举的十进制数转为等长二进制串，方便对应“选/不选”状态

3. 主逻辑解析（数组分组求最小差值）

cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i], sum += a[i]; // 输入数组，求总和sum
for (int i = 1; i < pow(2, n); i++){ // 枚举1~2ⁿ-1（所有非空组合）
    string s = tento(i); // 转二进制串
    int tem = 0;
    for (int j = 0; j < s.size(); j++){
        if (s[j] == '1') tem += a[j + 1]; // 二进制位为1，选中对应元素
    }
    ans = min(ans, abs(sum - tem - tem)); // 计算两组差值（sum-tem为另一组和）
}
cout<<ans;

• 枚举范围：1 ~ 2ⁿ - 1：避免全不选（i=0）的无效情况
• 差值计算：abs(sum - 2*tem)（sum=选的和+没选的和 → 没选的和=sum-tem → 差值=|(sum-tem)-tem|）
• 核心目标：遍历所有组合，找到最小差值

三、map容器（键值对容器）

1. 定义与本质

• 语法：map<键类型, 值类型> 变量名
• 示例：map<string, int> m;（键=字符串，值=整数）
• 本质：存储“键-值”对，键唯一（不能重复），可通过键快速查找值

2. 核心操作（逐行解析）

3. 关键特性

1. 自动排序：map会按“键”的大小自动升序排列（字符串按字典序，数字按数值）
   • 示例：存储顺序是Charlie→Bob→Alice，但遍历输出是Alice→Bob→Charlie
2. 时间复杂度：单次访问/插入/查找的时间复杂度为O(log n)（效率高于暴力遍历）
3. 易错点：直接用m["不存在的键"]检查存在性会创建新键，导致m.size()增加（如m["luohao"]会新增键"luohao"，值为0，size从3变4）

4. 遍历的另一种方式（迭代器，拓展）

// 兼容C++11之前的写法，与范围for等价
for (map<string, int>::iterator it = m.begin(); it != m.end(); it++) {
    cout << it->first << "  " << it->second << "\n"; // first=键，second=值
}

四、综合总结

核心知识点回顾

1. 二进制枚举：通过十进制数的二进制表示枚举所有组合，核心是“位对应选/不选”，适用于n较小（n≤20）的组合/分组问题，tento()函数是进制转换的核心工具；
2. map容器：键值对存储结构，查键存在性必须用m.count(键)（避免自动创建新键），会按键自动排序，单次操作时间复杂度O(log n)；
3. 核心易错点：直接访问map中不存在的键会自动创建该键，导致容器大小变化，务必用count()检查键的存在性。