题解

题目解析

• 输入输出：第一行输入两个整数 $N$（班级人数，编号 $0$ 到 $N-1$）和 $M$（报数总次数）；第二行输入 $M$ 个整数表示每次报出的编号。输出所有未到达同学的编号（升序，空格分隔）；若全部到达，则只输出一个整数 $N$。
• 数据范围：$2 \le N, M \le 100$，所有报出的编号均在 $[0, N-1]$ 范围内。
• 复杂度要求：数据规模极小，线性 $O(N+M)$ 时间复杂度和 $O(N)$ 空间复杂度即可轻松满足 $1\text{s}$ 时限与 $128\text{MB}$ 内存限制。
• 算法知识点：数组计数（桶思想）、简单模拟、集合差集

思路解析

1. 建立存在性标记：创建一个大小足够的计数数组 cnt（初始化为0），遍历 $M$ 次报数记录。对于每次报出的编号 $x$，执行 cnt[x]++。由于题目只关心"是否到达"而不关心次数，只要 cnt[x] > 0 即表示该同学已到达。
2. 遍历检查缺失：顺序扫描编号 $0$ 到 $N-1$。若 cnt[i] == 0，说明编号 $i$ 的同学从未报数，即未到达，立即输出该编号；同时用变量 ans 统计已到达的人数（即 cnt[i] > 0 的情况）。
3. 处理全到达情况：扫描结束后，若 ans == n，说明 $0$ 到 $N-1$ 所有编号均存在，按题意输出 $N$。

完整代码

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

int cnt[1000];  // 计数数组，下标对应同学编号，值表示该编号被报出的次数

int main(){
    int n, m;
    cin >> n >> m;
    // 步骤1：读入M次报数并统计每个编号的出现次数
    for (int i = 0; i < m; i++) {
        int x;
        cin >> x;
        cnt[x]++;  // 编号x被报出一次，计数+1（只要>0即表示该同学已到达）
    }
    int ans = 0;  // 统计实际到达的同学数量
    // 步骤2：遍历0~N-1，检查哪些编号从未出现（cnt[i]==0）
    for (int i = 0; i < n; i++) {
        if (cnt[i] == 0) 
            cout << i << " ";  // 未到达，输出编号（自动按0~N-1升序）
        else 
            ans++;  // 该编号存在，到达人数+1
    }
    // 步骤3：特殊判断：如果全部到达（ans等于总人数n），输出n
    if (ans == n) cout << n << endl;
    return 0;
}