正解:并查集
#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
int s[10 * N], a[N]; //s数组存储a[i]应该修改为的数
int n;
void init()
{
for (int i = 1; i < 10 * N; i++) s[i] = i;
}
int find(int x) //本体find操作表示找到x应该修改为的数
{
if (x == s[x]) return x;
return s[x] = find(s[x]);
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n;
init();
for (int i = 1; i <= n; i++)
{
cin >> a[i];
a[i] = find(a[i]); //修改a[i]
s[a[i]] = find(a[i] + 1); //当下一次找到a[i]时,该修改为的数就是a[i] + 1
}
for (int i = 1; i <= n; i++) cout << a[i] << ' ';
return 0;
}
记录错误做法
想法:对于每一个a[i],如果在并查集中自成一个结点,那么说明它没在之前的序列中出现过,则可以把它合并到a[1]上
于是利用find(a[i]) != a[i]
来检查一个数是否出现过,若出现过就a[i]++,直到a[i]未出现过,然后再将a[i]合并到a[1]上
虽然用到了并查集,也不像暴力做法,遍历前面所有点来查重
但本质上没什么区别
1 1 1 1 1 1
对于这样一组数据,在计算a[6]时, 数组前五项为{1, 2, 3, 4, 5}
对于a[6],仍然需要递增5次才能得到a[6] = 6
本质上还是O(n²)的复杂度
有点类似于在find操作中,由于链过长,find退化为O(n)时间复杂度
这时候可以对并查集数组做一点改动,让它存储a[i]应该修改为的数
例如find(a[i])应该返回a[i] + 1,所以s[a[i]] = find(a[i] + 1),这里也用了类似于路径压缩的思路,递归地修改s
for (int i = 1; i <= n; i++)
{
cin >> a[i];
}
for (int i = 2; i <= n; i++)
{
while (find(a[i]) == a[1]) a[i]++;
merge(a[i], a[1]);
}
for (int i = 1; i <= n; i++) cout << a[i] << ' ';
树状数组+二分
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
const int N = 100010;
int c[N];
int a[N];
int st[N];
int lowbit(int x)
{
return x & -x;
}
int n;
int sum(int x) //求[1, x]的和
{
int res = 0;
for (int i = x; i > 0; i -= lowbit(i)) res += c[i];
return res;
}
void add(int x, int y) //数列第x项加上y
{
for (int i = x; i <= n; i += lowbit(i)) c[i] += y;
}
int range_sum(int x, int y) //求[x, y]的和就等于[1, y] - [1, x - 1]
{
return sum(y) - sum(x - 1);
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = 1; i <= n; i++)
{
if (!st[a[i]])
{
st[a[i]] = 1;
add(a[i], 1);
}
else
{
int l = a[i], r = 1e5, mid;
while (l < r)
{
mid = l + r >> 1;
//[a[i], mid]中出现过的数的个数小于它们之间所有数的个数
//需要找到最小的,满足这样性质的点,a[i]就要修改为它
if (range_sum(a[i], mid) < mid - a[i] + 1) r = mid;
else l = mid + 1;
}
a[i] = r;
st[r] = 1;
add(a[i], 1);
}
}
for (int i = 1; i <= n; i++) cout << a[i] << ' ';
return 0;
}