1 条题解
-
0
编号归档:讲解
思路与 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
- 上传者