这是一道经典的计数/标记类题目。我们需要通过报出的编号来判断哪些人到了,哪些人没到。
题目分析
1. 核心目标:找出 000 到 N−1N-1N−1 中,哪些编号没有在输入的第二行中出现过。
2. 关键点:
* 编号范围是 000 到 N−1N-1N−1。
* 输入的第二行有 MMM 个数,代表报数的情况。
* 重复报数:题目提到“有的同学很顽皮,会多次报出”。这意味着输入的 MMM 个数中可能有重复。但这不影响我们的判断,只要出现过一次,就说明这个人到了。
3. 输出规则:
* 如果所有人都到了(即 000 到 N−1N-1N−1 都出现过),输出 NNN。
* 否则,从小到大输出没到的编号,用空格分隔。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
解题思路:标记法(桶的思想)
我们可以准备一个“名单表”(数组),用来记录每个人是否到了。
1. 初始化:创建一个大小为 NNN 的数组(或者布尔数组),全部初始化为 false(表示没到)。
2. 读取并标记:读取第二行的 MMM 个编号。每读到一个编号 xxx,就在数组的第 xxx 个位置打上标记(设为 true),表示编号为 xxx 的同学到了。
* 注:即使同一个编号被读到多次,反复标记为 true 也是没问题的。
3. 统计结果:遍历这个数组(从下标 000 到 N−1N-1N−1):
* 如果某个位置还是 false,说明这个编号的同学没到,把它记录下来。
4. 输出:
* 如果记录下来的“没到的人”数量为 0,说明全到了,输出 NNN。
* 否则,依次输出记录下来的编号。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
代码实现
C++ 代码
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
样例验证
样例 1:
* 输入:
* 过程:
* N=3N=3N=3,编号是 0, 1, 2。
* 报数有 0, 2, 1。
* 标记数组:arrived[0]=true, arrived[2]=true, arrived[1]=true。
* 检查:0, 1, 2 都到了。
* 输出: 所有人都到了,输出 NNN,即 3。
样例 2:
* 输入:
* 过程:
* N=3N=3N=3,编号是 0, 1, 2。
* 报数全是 0。
* 标记数组:arrived[0]=true (反复标记多次), arrived[1]=false, arrived[2]=false。
* 检查:编号 1 和 2 没到。
* 输出: 从小到大输出没到的编号,即 1 2。