GESP 题解库 / 3 级题解 / [GESP202306 三级] 春游 · 第 23 / 28 题
GESP202306 三级 · B3842 · 简单

春游

同学编号 0 ~ N−1,报号 M 次(可能重复),找出没到场的编号;若全到则输出 N。

📊
N, M ≤ 1000
数据规模
🔢
bool / int
数据类型
⚡
O(N + M)
时间复杂度
🎯
标记数组
核心算法
01
题目拆解
把题目拆成一块块,看清全貌

📝 题目原文

班上有 N 位同学,编号从 0 到 N − 1。老师让到场的同学报出自己的编号,报到的人可能重复报很多次。请找出没有到场的同学编号,按从小到大输出,空格分隔。

如果所有同学都到场,输出 N。

💡
人话翻译:准备 N 个"打卡格子",每听到一个编号就把对应格子打上勾(重复报也只是一个勾)。最后看哪些格子没打勾——那些就是没来的。注意"全到"要输出 N,而不是什么都不输出。

🔍 关键词提取

标记数组去重遍历输出特殊输出

已知条件

项目说明
输入第一行 N、M;第二行 M 个报出的编号
输出未到场编号(升序空格分隔),或 N(全到)
数据范围2 ≤ N, M ≤ 1000
编号范围小于 N 的非负整数
重复同一编号可能被报多次

需要解决的问题

02
思维导图
整理解题思路的全貌
✅ 打卡标记 + 扫一遍
📥 读入
N 位同学、M 次报号
编号 0 ~ N−1
可能大量重复
标记数组初始全 false
✅ 打标记
每读一个编号 x
arrived[x] = true
重复报不产生影响
O(M)
🔍 扫一遍
i 从 0 到 N−1
arrived[i] 为 false 就输出 i
升序自然满足
O(N)
⚠️ 特殊要求
全到时要输出 N
不是输出空行
也不是输出 0
行末不加空格
03
样例手算推导
样例两组对照

🧮 样例 1:N = 3,报号 0 2 1

三个编号都被报过,说明全到。

报号标记情况
0arrived[0] = true
2arrived[2] = true
1arrived[1] = true
1
扫描 0 ~ 2

arrived[0] = true → 跳过

arrived[1] = true → 跳过

arrived[2] = true → 跳过

一个都没输出

✅ 触发"全到"规则,输出 N = 3

输出:3 ✓

🧮 样例 2:N = 3,报号 0 0 0 0 0

五次数都报的是 0 号,1 号和 2 号没来。

报号标记情况说明
第 1 次 0arrived[0] = true
第 2 ~ 5 次 0arrived[0] 已经是 true重复报不影响结果
1
扫描 0 ~ 2

arrived[0] = true → 跳过

arrived[1] = false → 输出 1

arrived[2] = false → 输出 2

✅ 输出 1 2

输出:1 2 ✓

🔑
"重复报"是这题的干扰项:标记数组天然去重——同一个编号报一百次,arrived 也只是一个 true。所以不需要任何额外去重逻辑。
04
解法对比
标记数组 vs 计数排序思想

⚔️ 解法对比

🟢 布尔标记数组(推荐) 推荐

用 arrived[N] 记录到场情况,扫一遍输出未到

  • 时间 O(N + M)
  • 空间 O(N)
  • 天然去重
  • 代码 15 行
💡
为什么推荐:编号范围恰好是 0 ~ N−1,和数组下标一一对应,这是"用数组当集合"的教科书用法。

🟠 用 set 容器

把报到的编号插入 set,最后检查哪些不在里面

  • 时间 O(M log M)
  • 空间比数组大
  • 功能上等价
  • 本题属于杀鸡用牛刀
⚠️
什么时候用 set:当编号范围很大或稀疏时(比如编号可能到 10⁹),数组开不下才需要 set。本题 N ≤ 1000,数组最简单。

📈 性能对比

方案时间代码量
布尔数组O(N + M)约 15 行
set 容器O(M log M)约 20 行
05
算法流程图
先打标记,再扫一遍
开始读入 N、M;arrived[0..N−1] 全部置 false读入 M 个编号,逐个把 arrived[x] 置为 truefound = false;i 从 0 到 N−1 扫描arrived[i] 为 false 吗?是 ✓输出编号 i,found 置真否 ✗跳过有没有输出过任何编号?输出过结束一个都没输出输出 N结束还有编号没检查 → i 加 1
← 左右滑动查看完整流程图
06
动手算一算
自己输入数据试试看

✅ 到场情况统计器

第一行输入 N 和 M,第二行输入 M 个报出的编号,程序会列出未到场的同学。

结果会显示在这里

点按钮开始 →

07
代码精讲
逐段拆解,彻底搞懂

💻 完整 C++ 代码

#include <bits/stdc++.h>
using namespace std;

bool arrived[1005];

int main() {
    int N, M;
    scanf("%d %d", &N, &M);

    for (int i = 0; i < M; i++) {
        int x;
        scanf("%d", &x);
        arrived[x] = true;       // 重复报也只标记一次
    }

    bool anyMissing = false;
    bool first = true;
    for (int i = 0; i < N; i++) {
        if (!arrived[i]) {
            if (!first) printf(" ");
            printf("%d", i);
            first = false;
            anyMissing = true;
        }
    }

    if (!anyMissing) printf("%d", N);    // 全到:输出 N
    printf("\n");
    return 0;
}
🔑
这道题唯一的"陷阱"是那个特殊输出:当所有同学都到场时,题目要求输出 N。如果不加这个分支,程序会输出一个空行,直接判错。读题时一定要把"如果……则……"这类特殊规则圈出来。

📖 关键几行怎么看

代码作用为什么这样写
arrived[x] = true标记到场直接置真,无需判断之前是否已标记
if (!arrived[i])找未到场从 0 到 N−1 扫描保证升序
if (!first) printf(" ")控制空格避免行末和行首多余空格
if (!anyMissing) printf("%d", N)特殊输出全到时输出 N,这是题目规定的
⚠️
三个坑:① 忘了"全到输出 N"这条特殊规则;② 输出时用 printf("%d ", i) 导致行末多空格(多数评测能过,但严格比对会错);③ 数组开成 N 大小却访问下标 N−1 之外(本题保证编号 < N,安全)。
08
边界测试 & 易错点
把坑都踩一遍,考试不翻车

🧪 边界测试用例表

写完程序后,用这些数据自查一遍:

输入答案考察点
3 3
0 2 1
3题面样例 1:全到输出 N
3 5
0 0 0 0 0
1 2题面样例 2
2 2
0 1
2最小规模,全到
3 2
0 0
1 2只有 0 到场
4 4
1 1 2 2
0 3首尾两位没到,输出应按编号升序
✅
自查清单:① 用标记数组去重了吗?② 输出是从小到大吗?③ 全到时输出 N 了吗?

🚨 易错点清单

⚠️
忘记"全到输出 N":这样样例 1 会输出一个空行,直接判错。
⚠️
输出顺序没保证:必须从编号 0 开始扫描,才能保证从小到大;不能按报号顺序输出。
⚠️
把"重复报"当成需要特殊处理:布尔数组天然去重,不需要任何额外判断。
09
复杂度分析
算算效率怎么样

📊 复杂度四宫格

时间复杂度
O(N + M)
空间复杂度
O(N)
N, M 最大
1000
运算量
2000 次

时间怎么算的?

空间都用在哪?

一个长度为 N 的布尔数组记录到场情况。

✅ 数据规模很小,任何写法都瞬间完成;这题的考点是"重复报号"的干扰和"全到输出 N"的特殊规则。

10
知识拓展
学一道题,会一类题

🔗 常用技巧小抄

// 用数组当"集合"的标准写法(编号范围 [0, N) 时最省事)
bool inSet[1005];
inSet[x] = true;               // 插入
if (inSet[x]) { /* 存在 */ }   // 查询

// 输出时避免行末空格
bool first = true;
for (int i = 0; i < N; i++) {
    if (cond(i)) {
        if (!first) printf(" ");
        printf("%d", i);
        first = false;
    }
}

// 当值域很大时改用 set 或 map
set<int> st;
st.insert(x);
if (st.count(x)) { /* 存在 */ }

🌟 举一反三

把这道题用到的基本功拆出来,它们能迁移到很多同类问题上。

能力点本题怎么用还能迁移到
标记数组用下标当集合元素去重、存在性判断、计数
升序输出从 0 扫到 N−1所有要求"按编号从小到大输出"的题
特殊输出规则"如果……则输出……"读题时务必圈出这类附加规则
🌟
思考题:如果题目改成"输出到场次数恰好为 1 次的编号",标记数组就不够用了——该怎么改?(提示:把 bool 换成 int 计数数组,统计每个编号被报了几次,最后筛出计数等于 1 的。)