【GESP】C++三级真题 luogu-B3842 [GESP202306 三级] 春游

GESP三级真题，一维数组应用（C++三级大纲中5号知识点，一维数组），难度★✮☆☆☆。

luogu-B3842 [GESP202306 三级] 春游

题目要求

题目描述

老师带领同学们春游。已知班上有 $N$ 位同学，每位同学有从 $0$ 到 $N-1$ 的唯一编号。到了集合时间，老师确认是否所有同学都到达了集合地点，就让同学们报出自己的编号。到达的同学都会报出自己的编号，不会报出别人的编号，但有的同学很顽皮，会多次报出。你能帮老师找出有哪些同学没有到达吗 ?。

输入格式

输入包含 $2$ 行。第一行包含两个整数 $N$ 和 $M$，表示班级有 $N$ 位同学，同学们共有 $M$ 次报出编号。约定 $2 \le N,M \le 1000$。
第二行包含 $M$ 个整数，分别为 $M$ 次报出的编号。约定所有编号是小于 $N$ 的非负整数。

输出格式

输出一行。如果所有同学都到达，则输出 $N$；否则由小到大输出所有未到达的同学编号，空格分隔。

输入输出样例 #1

输入 #1

3 3
0 2 1

输出 #1

3

输入输出样例 #2

输入 #2

3 5
0 0 0 0 0

输出 #2

1 2

---

题目分析

解题思路

1. 题目要求统计班级中未到达集合地点的学生编号。

2. 解题关键点：
   • 使用数组记录每个学生是否到达
   • 处理重复报数的情况
   • 按顺序输出未到达学生的编号
   • 特殊情况处理（所有学生都到达时）
3. 具体思路：
   • 读取班级人数N和报数次数M
   • 创建长度为N的布尔数组，记录每个学生的到达状态
   • 遍历M次报数，将对应学生标记为已到达
   • 遍历学生编号数组：
     • 如果学生未到达，输出其编号
     • 如果所有学生都到达，输出N
4. 时间复杂度分析：
   • 需要遍历报数序列一次，时间复杂度O(M)
   • 需要遍历学生数组一次，时间复杂度O(N)
   • 总体时间复杂度为O(M+N)
   • 空间复杂度为O(N)，需要存储学生到达状态数组

---

示例代码

#include <iostream>

int main() {
    // 声明变量n表示班级人数，m表示报数次数
    int m, n;
    std::cin >> n >> m;
    // 创建长度为n的数组n_ary，用于标记每个学生是否到达，初始化为0
    int n_ary[n] = {0};
    // 创建长度为m的数组m_ary，用于存储报数序列
    int m_ary[m];
    // 读入m个报数
    for (int i = 0; i < m; i++) {
        std::cin >> m_ary[i];
    }
    // 遍历报数序列，将已到达的学生标记为1
    for (int i = 0; i < m; i++) {
        n_ary[m_ary[i]] = 1;
    }
    // flag用于标记是否所有学生都到达，初始假设都到达
    bool flag = true;
    // 遍历n_ary数组，输出未到达的学生编号
    for (int i = 0; i < n; i++) {
        if (n_ary[i] == 0) {
            std::cout << i << " ";
            flag = false;
        }
    }
    // 如果所有学生都到达，输出班级总人数n
    if (flag) {
        std::cout << n;
    }
    return 0;
}

---

所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code

GESP各级别考纲要点、知识拓展和练习题目清单详见C++学习项目主页

“luogu-”系列题目已加入洛谷Java、C++初学团队，作业清单，可在线评测，团队名额有限，欢迎加入。

“bcqm-”系列题目可在编程启蒙题库进行在线评测。