春游 题解

题目分析

本题要求统计哪些同学没有到达集合地点。班级有 N 位同学，编号从 0 到 N-1。同学们总共报了 M 次编号，但有些同学可能报多次，有些同学可能一次都没报。我们需要找出所有未报到的同学编号，由小到大输出；如果所有人都报了（至少一次），则输出 N。

题目的核心是判断每个编号是否至少出现过一次，属于典型的“标记统计”问题。

数据范围：2 ≤ N, M ≤ 1000，数据量很小，可以使用简单的数组进行标记。

解题思路

1. 用布尔数组记录报到情况
   建立一个长度为 N 的布尔数组 arrive，arrive[i] 表示编号为 i 的同学是否报过到。初始时所有元素设为 false。

2. 读入报到信息并标记
   遍历 M 次报到的编号，每读入一个编号 code，就将 arrive[code] 设为 true。因为同一个同学可能多次报到，重复设置为 true 不会有影响。

3. 检查未报到的同学
   遍历 0 到 N-1，找到所有 arrive[i] == false 的编号，按顺序输出。

   • 如果从未输出过未报到同学，直接输出该编号；
   • 否则在前面加一个空格再输出，以满足空格分隔的要求。

4. 处理全部到达的情况
   设置一个标志变量 all，初始为 true。如果遍历过程中发现任何一个未报到的同学，就将 all 置为 false。遍历结束后，若 all 仍为 true，说明所有同学都到达了，此时输出 N。

5. 输出换行
   最后输出换行符，保证格式完整。

算法说明

算法流程非常直观，本质上是一个“计数”或“存在性判断”问题。由于只关心是否出现过，不关心次数，因此布尔标记足矣。

步骤细化：

• 初始化标记数组。
• 读入并标记。
• 遍历查找并输出未报到同学。
• 特殊情况输出。

该算法不需要排序，因为我们是按编号 0 到 N-1 顺序检查的，天然保证了从小到大的输出顺序。

复杂度分析

• 时间复杂度：
  初始化数组需要 O(N)，读入 M 次报到需要 O(M)，最后检查所有 N 位同学需要 O(N)。总体时间复杂度为 O(N + M)。
  对于本题 N, M ≤ 1000，完全可以接受。

• 空间复杂度：
  需要一个长度为 N 的布尔数组，空间复杂度为 O(N)。
  参考代码中数组大小固定为 1000，可以满足题目最大范围。

代码解释

下面给出参考代码，并逐段解释。

cpp
复制
1#include <iostream>
2using namespace std;
3bool arrive[1000];
4int main() {
5    int n = 0, m = 0;
6    cin >> n >> m;
7    // 初始化 arrive 数组为所有同学均未报到
8    for (int i = 0; i < n; i++)
9        arrive[i] = false;
10    // 依次报到 m 次
11    for (int i = 0; i < m; i++) {
12        int code = 0;
13        cin >> code;
14        arrive[code] = true;
15    }
16    // 依次检查 n 位同学是否到达
17    bool all = true;
18    for (int i = 0; i < n; i++) {
19        if (!arrive[i]) {
20            if (all) {
21                cout << i;
22                all = false;
23            } else {
24                cout << " " << i;
25            }
26        }
27    }
28    // 处理全部到达的特殊情况
29    if (all)
30        cout << n;
31    cout << endl;
32    return 0;
33}

代码解析：

• arrive 数组用于标记，声明在全局区自动初始化为 false，但代码中显式初始化了前 n 个元素，保证逻辑清晰。
• 第一个循环读入 m 次报到编号，并将对应位置设为 true。
• 第二个循环用 all 变量记录是否曾输出过未报到的同学。初始 all = true。
• 当发现 !arrive[i]（该同学未报到）时：
  • 若 all 为 true，表示这是第一个未报到的同学，直接输出编号，并将 all 置为 false。
  • 否则输出空格加编号，保证编号间用空格隔开。
• 循环结束后，如果 all 仍为 true，说明遍历过程中从未进入 if (!arrive[i]) 分支，即所有同学都报到了，此时输出 N。
• 最后输出换行。

常见易错点

1. 输出格式
   未报到同学的编号之间要用空格分隔，但行末不能有多余空格。代码通过判断 all 标记来控制第一个编号前不输出空格，后面都在编号前加空格，完美解决了此问题。

2. 全部到达时输出什么
   题目要求“如果所有同学都到达，则输出 N”。注意不是输出 n 个数字，而是输出数值 N 本身。示例代码中用 cout << n; 正确处理了这种情况。

3. 编号范围
   题目保证编号是小于 N 的非负整数，因此数组访问不会越界。但实际编程时仍需注意数组大小至少为 N。

总结

本题是一道非常基础的标记与统计练习题，主要考察循环、数组的简单应用以及输出格式的控制。对于初学者，通过本题可以巩固布尔数组标记、条件判断和顺序输出等基本技能。