雪人部落关灯问题 C++ 实现及分析

好的，这道题是一个典型的区间覆盖问题，我们一起来分析并实现它。 ## 🧠 问题分析 题目描述的是： 有 **10盏灯**，编号从 **1 到 10**，初始全部 **亮着**。 每次操作给定一个 **起点** 和 **终点**，会把 **从起点到终点之间所有的灯熄灭**。 一共进行 **两次** 操作。 最终要求输出 **还亮着的灯的数量**。 **关键点理解**： - 灯一开始全部亮着。 - 每次操作会熄灭一个 **闭区间** 内的所有灯（包括起点和终点）。 - 如果两次操作的区间有重叠，重叠部分也只会被熄灭一次（已经灭了，不能再灭一次）。 - 最终亮着的灯就是没有被任何一次操作覆盖到的灯。 --- ## 🧪 输入输出示例解读 输入： ``` 1 4 4 6 ``` 第一次操作：熄灭 1, 2, 3, 4 第二次操作：熄灭 4, 5, 6 两次操作覆盖的灯集合：{1,2,3,4,5,6} 一共 10 盏灯，覆盖 6 盏，剩余亮着的灯：4 盏（7,8,9,10） 输出： ``` 4 ``` --- ## 🎯 解题思路 有多种思路可以实现： ### ✅ 思路一：布尔数组模拟（推荐，简单直观） 1. 创建一个大小为 11 的布尔数组（索引从1开始），全部初始化为 `true`（亮）。 2. 对每组输入的起点和终点，将数组中该范围内的元素设为 `false`（灭）。 3. 最后统计数组中 `true` 的个数并输出。 **优点**：代码简单，易于理解，适合初学者。 **缺点**：如果灯的数量很大（比如10万），这个方法仍然非常高效，因为操作次数固定为2。 --- ### ✅ 思路二：区间合并法（适合更一般的多次区间覆盖问题） 1. 将两次操作的区间收集起来。 2. 如果区间重叠，合并它们。 3. 计算所有合并后区间的总长度（覆盖的灯数）。 4. 亮着的灯数 = 10 - 覆盖的灯数。 **优点**：适用于更多次操作或更复杂的区间问题，扩展性强。 **缺点**：对于本题来说略复杂。 --- ## 👨‍💻 C++ 代码实现（思路一） ```cpp #include <iostream> #include <vector> using namespace std; int main() { // 灯的初始状态，true表示亮，false表示灭 // 下标0不使用，下标1~10表示第1~10盏灯 vector<bool> lights(11, true); int start, end; // 第一次操作 cin >> start >> end; for (int i = start; i <= end; i++) { lights[i] = false; } // 第二次操作 cin >> start >> end; for (int i = start; i <= end; i++) { lights[i] = false; } // 统计亮着的灯的数量 int count = 0; for (int i = 1; i <= 10; i++) { if (lights[i]) { count++; } } cout << count << endl; return 0; } ``` --- ## 🧵 代码详解 | 代码部分 | 说明 | |---------|------| | `vector<bool> lights(11, true);` | 创建一个大小为 11 的布尔向量，初始值为 `true`，下标 0 不用，下标 1~10 代表 10 盏灯 | | `for (int i = start; i <= end; i++)` | 遍历从 `start` 到 `end` 的每一个灯，将其熄灭 | | `if (lights[i])` | 判断灯是否还亮着 | | `count++` | 统计亮着的灯数 | --- ## 🔔 几点开发建议 1. **边界问题**：注意题目中起点和终点是 **包含端点** 的，循环条件要用 `<=`。 2. **数组下标**：如果从 0 开始编号，可以简化，但本题从 1 开始更符合题意，便于理解。 3. **输入验证**：实际开发中应验证起点 ≤ 终点，以及范围在 1~10 之间，但本题可假设输入合法。 4. **内存考虑**：`vector<bool>` 是 C++ 中特化的模板，每个元素只占 1 位，非常节省内存。 5. **扩展性**：如果灯的数量变化，例如有 N 盏灯，只需修改数组大小和统计范围即可，代码逻辑不变。 --- ## 🧠 进阶思考 如果雪人不是只操作两次，而是操作 **很多次**（例如 1000 次），该怎么办？ - 可以用 **差分数组** 或 **扫描线算法**，在 O(N+M) 时间内处理任意多次区间覆盖，其中 N 是灯数，M 是操作次数。 - 对于本题（仅两次），直接模拟即可，代码最简洁。 --- ## 📚 相关知识点 - **区间覆盖 / 区间合并**：常见于编程竞赛题，如计蒜客、洛谷等。 - **数组模拟**：基础但实用的技巧。 - **布尔向量**：C++ 中 `vector<bool>` 的特殊用法。 --- ## ❓ 常见问题（FAQ） **Q：如果区间完全重叠怎么办？** A：不影响，因为灯已经被熄灭一次，再次熄灭不会改变状态。 **Q：如果起点大于终点怎么办？** A：题目未明确说明，但通常可以假设起点 ≤ 终点，或者交换两者。 **Q：可以用 Set 存储亮着的灯吗？** A：可以，但数组模拟更高效、更简单。 --- ######[AI写代码神器 | 1306点数解答 | 2026-05-23 21:05:04]