G3001 [GESP202306 三级] 春游 题解

知识点：一维数组、标记、集合差。

解题思路

用长度n的标记数组记录已经上车的学生编号，再递增输出没有标记的人；若全到齐则输出n。

为什么正确

每个编号的标记精确表示是否出现，扫描补集正好得到未到齐名单。

易错点

编号从0到n-1；重复出现的上车编号只标记一次。

复杂度

时间O(n+m)，空间O(n)。

参考代码（C++17）

#include<bits/stdc++.h>

using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m,x;
    cin>>n>>m;
    vector<int>a(n);
    while(m--) {
        cin>>x;
        a[x]=1;
    }
    bool all=true;
    for(int i=0;i<n;i++)if(!a[i]) {
        cout<<i<<" ";
        all=false;
    }
    if(all)cout<<n;
}

说明

本题解为配套教学整理，非官方题解。复杂度按本页参考实现计算，题库使用6个自行生成的测试点。