1 条题解

  • 0
    @ 2026-11-16 20:48:26

    编号归档:讲解

    思路与 STL 接口

    方案一:vector 读入后 sort,unique 把相邻重复元素移到逻辑尾部,随后 erase(unique(...),end()) 才真正缩小容器。方案二:逐个插入 set,set 自动去重且升序迭代。

    复杂度

    sort+unique+erase 总时间 O(n log n),额外存储 O(n)。set 方案时间 O(n log n)、空间 O(k)。

    常见错误

    unique 不会改变 vector 的 size;只调用 unique 而不 erase 会输出无效尾段;未排序就 unique 只能去掉相邻重复。

    验证方法

    Python oracle 独立读取操作并模拟或排序,不调用标准程序。正式数据含手算样例、边界、固定种子随机和两个最大规模用例;另做 200 次小规模差分,验证器拒绝非法状态和多余 token。common_wrong.cpp 保留上述一种常见逻辑错误,正式数据必须能够拒绝它。

    C++17 参考实现

    #include <bits/stdc++.h>
    using namespace std;
    int main(){ios::sync_with_stdio(false);cin.tie(nullptr);int n;cin>>n;vector<long long>a(n);for(auto&x:a)cin>>x;sort(a.begin(),a.end());a.erase(unique(a.begin(),a.end()),a.end());cout<<a.size()<<'\n';for(size_t i=0;i<a.size();++i)cout<<(i?" ":"")<<a[i];cout<<'\n';}
    
    
    • 1

    信息

    ID
    5256
    时间
    2000ms
    内存
    256MiB
    难度
    1
    标签
    递交数
    1
    已通过
    1
    上传者