题目描述
blablabla
样例
blablabla
算法1
(set+二分)
由于事先需要插入的元素太多,插入1000000个元素会TLE,所以只能先插入100000个元素,过9/11的数据(呜呜呜……)
C++ 代码
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <set>
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
int n;
int a[100010];
set<int> s;
int main()
{
cin >> n;
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
for (int i = 1; i <= 100000; i++) s.insert(i);
cout << a[1] << ' ';
s.erase(a[1]);
for (int i = 2; i <= n; i++)
{
if (s.count(a[i]))
{
cout << a[i] << ' ';
s.erase(a[i]);
}
else
{
auto it = s.lower_bound(a[i]);//查找没有出现的第一个比a[i]大的元素
cout << *it << ' ';
s.erase(*it);
}
}
return 0;
}
算法2
(并查集)
并查集使用:每个元素初始时指向大于等于自己且没有被使用过的第一个元素,初始时每个元素均指向自己,即如果要找下一个没出现过的点就找跟结点,因为并查集的路径压缩,保证了同样的搜索顺序只会执行一次
C++ 代码
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <set>
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
int n;
int a[100010];
int p[1000010];
int find(int x)
{
if(p[x]==x) return x;
return p[x]=find(p[x]);
}
int main()
{
cin >> n;
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
for (int i = 1; i <= 1000000; i++) p[i]=i;
for (int i = 1; i <= n; i++)
{
int anc=find(a[i]);//找a[i]的祖先,即第一个比它大且没出现过的元素
cout<<anc<<' ';
p[anc]=anc+1;//之前把a[i]修改为了它的祖先,故这个祖先已经出现过了,需要更改祖先节点的父节点
}
return 0;
}
算法3
(树状数组+二分)
C++ 代码
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <set>
#define N 1000000
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
int n;
int a[100010];
int tree[N];//树状数组
//树状数组的单修区查
//设一个初始化全为0的bool数组b,b[i]=true表示a[i]已经出现过
int lowbit(int x)
{
return x&-x;
}
void add(int x,int k)//在b[i]上加k
{
for(int i=x;i<=N;i+=lowbit(i)) tree[i]+=k;
}
int query(int x)//查询区间[1,x]上b[]的和
{
int res=0;
for(int i=x;i;i-=lowbit(i)) res+=tree[i];
return res;
}
int main()
{
cin >> n;
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
for (int i = 1; i <= n; i++)
{
int l=a[i],r=N;
int ans=0;
while(l<=r)
{
int mid=l+r>>1;
if(query(mid)-query(l-1)==mid-l+1)//说明a[l~mid]中所有数都已经出现过,则要更改为的数一定不在这个区间内
{
l=mid+1;
}
else
{
ans=mid;
r=mid-1;
}
}
cout<<ans<<' ';
add(ans,1);
}
return 0;
}