同学编号 0 ~ N−1,报号 M 次(可能重复),找出没到场的编号;若全到则输出 N。
班上有 N 位同学,编号从 0 到 N − 1。老师让到场的同学报出自己的编号,报到的人可能重复报很多次。请找出没有到场的同学编号,按从小到大输出,空格分隔。
如果所有同学都到场,输出 N。
标记数组去重遍历输出特殊输出
| 项目 | 说明 |
|---|---|
| 输入 | 第一行 N、M;第二行 M 个报出的编号 |
| 输出 | 未到场编号(升序空格分隔),或 N(全到) |
| 数据范围 | 2 ≤ N, M ≤ 1000 |
| 编号范围 | 小于 N 的非负整数 |
| 重复 | 同一编号可能被报多次 |
arrived[编号] = true,重复报也无所谓三个编号都被报过,说明全到。
| 报号 | 标记情况 |
|---|---|
| 0 | arrived[0] = true |
| 2 | arrived[2] = true |
| 1 | arrived[1] = true |
arrived[0] = true → 跳过
arrived[1] = true → 跳过
arrived[2] = true → 跳过
一个都没输出
✅ 触发"全到"规则,输出 N = 3
输出:3 ✓
五次数都报的是 0 号,1 号和 2 号没来。
| 报号 | 标记情况 | 说明 |
|---|---|---|
| 第 1 次 0 | arrived[0] = true | |
| 第 2 ~ 5 次 0 | arrived[0] 已经是 true | 重复报不影响结果 |
arrived[0] = true → 跳过
arrived[1] = false → 输出 1
arrived[2] = false → 输出 2
✅ 输出 1 2
输出:1 2 ✓
用 arrived[N] 记录到场情况,扫一遍输出未到
把报到的编号插入 set,最后检查哪些不在里面
| 方案 | 时间 | 代码量 |
|---|---|---|
| 布尔数组 | O(N + M) | 约 15 行 |
| set 容器 | O(M log M) | 约 20 行 |
第一行输入 N 和 M,第二行输入 M 个报出的编号,程序会列出未到场的同学。
点按钮开始 →
#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,这是题目规定的 |
printf("%d ", i) 导致行末多空格(多数评测能过,但严格比对会错);③ 数组开成 N 大小却访问下标 N−1 之外(本题保证编号 < N,安全)。写完程序后,用这些数据自查一遍:
| 输入 | 答案 | 考察点 |
|---|---|---|
3 3 | 3 | 题面样例 1:全到输出 N |
3 5 | 1 2 | 题面样例 2 |
2 2 | 2 | 最小规模,全到 |
3 2 | 1 2 | 只有 0 到场 |
4 4 | 0 3 | 首尾两位没到,输出应按编号升序 |
一个长度为 N 的布尔数组记录到场情况。
✅ 数据规模很小,任何写法都瞬间完成;这题的考点是"重复报号"的干扰和"全到输出 N"的特殊规则。
// 用数组当"集合"的标准写法(编号范围 [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 | 所有要求"按编号从小到大输出"的题 |
| 特殊输出规则 | "如果……则输出……" | 读题时务必圈出这类附加规则 |
bool 换成 int 计数数组,统计每个编号被报了几次,最后筛出计数等于 1 的。)