数组标记法

这是一道经典的计数/标记类题目。我们需要通过报出的编号来判断哪些人到了，哪些人没到。

题目分析

1. 核心目标：找出 $0$ 到 $N-1$ 中，哪些编号没有在输入的第二行中出现过。
2. 关键点：
   • 编号范围是 $0$ 到 $N-1$。
   • 输入的第二行有 $M$ 个数，代表报数的情况。
   • 重复报数：题目提到“有的同学很顽皮，会多次报出”。这意味着输入的 $M$ 个数中可能有重复。但这不影响我们的判断，只要出现过一次，就说明这个人到了。
3. 输出规则：
   • 如果所有人都到了（即 $0$ 到 $N-1$ 都出现过），输出 $N$。
   • 否则，从小到大输出没到的编号，用空格分隔。

---

解题思路：标记法（桶的思想）

我们可以准备一个“名单表”（数组），用来记录每个人是否到了。

1. 初始化：创建一个大小为 $N$ 的数组（或者布尔数组），全部初始化为 false（表示没到）。
2. 读取并标记：读取第二行的 $M$ 个编号。每读到一个编号 $x$，就在数组的第 $x$ 个位置打上标记（设为 true），表示编号为 $x$ 的同学到了。
   • 注：即使同一个编号被读到多次，反复标记为 true 也是没问题的。
3. 统计结果：遍历这个数组（从下标 $0$ 到 $N-1$）：
   • 如果某个位置还是 false，说明这个编号的同学没到，把它记录下来。
4. 输出：
   • 如果记录下来的“没到的人”数量为 0，说明全到了，输出 $N$。
   • 否则，依次输出记录下来的编号。

---

代码实现

C++ 代码

#include<iostream>
using namespace std;
int a[1001]={0},b[1001]={0};
int main()
{
    int n,m;
    cin>>n>>m;
    bool f=true;

    for(int i=0;i<m;i++)
    {
        cin>>a[i];
        b[a[i]]+=1;
    }
    for(int i=0;i<n;i++)
    {
        if(b[i]==0)
        {
            f=false;
            cout<<i<<" ";
        }
    }
    if(f==true)
        cout<<n;
    return 0;
}

---

样例验证

样例 1:

• 输入:

  3 3
  0 2 1
  

• 过程:
  • $N=3$，编号是 0, 1, 2。
  • 报数有 0, 2, 1。
  • 标记数组：arrived[0]=true, arrived[2]=true, arrived[1]=true。
  • 检查：0, 1, 2 都到了。
• 输出: 所有人都到了，输出 $N$，即 3。

样例 2:

• 输入:

  3 5
  0 0 0 0 0
  

• 过程:
  • $N=3$，编号是 0, 1, 2。
  • 报数全是 0。
  • 标记数组：arrived[0]=true (反复标记多次), arrived[1]=false, arrived[2]=false。
  • 检查：编号 1 和 2 没到。
• 输出: 从小到大输出没到的编号，即 1 2。