---------------------------------以下是主题部分------------------------
- 要让一个数成为序列的模,那么这个数在之前序列出现的次数一定最多(或者是出现次数最多的数之一),那么我们只需要构造一个所有数出现次数都为1的序列,就能让所有的数都成为序列的模而不论在序列中的顺序。
- 而对于每个a[i]我们都要使其为b[1]-b[i]的模,我们只需要保证b[1]-b[i]之中出现一次a[i]就可以满足条件。所以对于长度为n的数组我们要让b数组1-n都出现一次。对于每个a[i],如果在b数组还未出现,那么b[i]就赋值为a[i],如果已经出现过,那么b数组就随意增加一个还没出现过的数即可。
- 我们可以用set来完成, 就能方便进行增删操作。
-----------------------以下是代码部分------------------------------------
#include <cstring>
#include <set>
#include <queue>
#define N 200005
using namespace std;
int a[N];
int p=200000;
queue<int> ans;
set<int> vis;
int main(){
int t;cin>>t;
while(t--){
int n;
cin>>n;
for(int i=1;i<=n;i++){
vis.insert(i);
}
for(int i=1;i<=n;i++){
cin>>a[i];
if(vis.find(a[i])!=vis.end()){
ans.push(a[i]);
vis.erase(vis.find(a[i]));
// cout<<"find::"<<endl;
// for(auto it=vis.begin();it!=vis.end();it++){
// cout<<*it<<" ";
// }
//cout<<endl;
}
else{
ans.push(*vis.begin());
vis.erase(vis.begin());
}
}
while(!ans.empty()){
cout<<ans.front()<<" ";
ans.pop();
}
cout<<endl;
vis.clear();
}
return 0;
}
------------------以下是反思部分--------------------------------
- 因为set是自带排序功能的,所以不能用来存b数组,用queue存或者数组存都行。
- 没有想到只需要让每个数出现次数都为1就可以方便地保证其为序列的模。